对于100%的数据，n≤4000，m≤100000，1≤li≤100000

题解：首先建出最短路径树。

            对于一条不在最短路径树里的边,设该边的两端点为x,y.t为x和y的最近公共祖先,dis[i]表示1到i的最短距离.

            那么对于x和t之间的点u,一定存在1-t-y-x-u的路径。路径长度为d[y]+v(x,y)+d[x]-d[u].

            我们需要最小化d[x]+d[y]+v(x,y).y和t之间的点同理。

            所以我们枚举每一条不在最短路径树里的边.更新两端点和lca之间的点即可。

            这些显然可以用树链剖分解决。

代码：

#include
    
     #include
     
      #include
      
       #define N 100010int pos[N],bl[N],point[N],next[N],t[N*4],p[N*4],size[N];int f,cnt,num,sz,n,m,x,y,w,fa[N][20],dis[N],deep[N];struct use{int st,en,w;}e[N];struct use2{int st,en,w;}b[N];using namespace std;void add(int x,int y,int w){next[++cnt]=point[x];point[x]=cnt;e[cnt].en=y;e[cnt].w=w;}void dfs(int x){  size[x]=1;  for (int i=1;(1<
       
        <=deep[x];i++) fa[x][i]=fa[fa[x][i-1]][i-1];  for (int i=point[x];i;i=next[i])   if (e[i].en!=fa[x][0]){      deep[e[i].en]=deep[x]+1;dis[e[i].en]=dis[x]+e[i].w;	  fa[e[i].en][0]=x;dfs(e[i].en);size[x]=size[x]+size[e[i].en];    }} void dfs2(int x,int c){ pos[x]=++sz;bl[x]=c;int k(0); for (int i=point[x];i;i=next[i])  if (e[i].en!=fa[x][0]&&size[e[i].en]>size[k]) k=e[i].en; if (!k) return;dfs2(k,c); for (int i=point[x];i;i=next[i])  if (e[i].en!=fa[x][0]&&e[i].en!=k) dfs2(e[i].en,e[i].en);}int lca(int x,int y){  if (deep[x]
        
         =0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];  if (x==y) return x;else return fa[x][0]; }void paint(int k,int v){t[k]=min(t[k],v);p[k]=min(p[k],v);}void pushdown(int k,int v){paint(k<<1,v);paint(k<<1|1,v);p[k]=t[0];} void add(int k,int l,int r,int ll,int rr,int v){  int mid=(l+r)>>1;  if (p[k]) pushdown(k,p[k]);  if (ll<=l&&r<=rr){paint(k,v);return;}  if (ll<=mid) add(k<<1,l,mid,ll,rr,v);  if (rr>mid) add(k<<1|1,mid+1,r,ll,rr,v);  t[k]=min(t[k<<1],t[k<<1|1]);	}int ask(int k,int l,int r,int x){ int mid=(l+r)>>1; if (p[k]) pushdown(k,p[k]); if (l==r) return t[k]; if (x<=mid) return ask(k<<1,l,mid,x); else return ask(k<<1|1,mid+1,r,x);}void solveadd(int x,int y,int v){  while(bl[x]!=bl[y]){     add(1,1,sz,pos[bl[x]],pos[x],v);     x=fa[bl[x]][0];  }  if (x!=y) add(1,1,sz,pos[y]+1,pos[x],v); }void solve(){  for (int i=1;i<=num;i++){  	int f=lca(b[i].st,b[i].en);  	solveadd(b[i].st,f,dis[b[i].en]+b[i].w+dis[b[i].st]);  	solveadd(b[i].en,f,dis[b[i].en]+b[i].w+dis[b[i].st]);  }	  for (int i=2;i<=n;i++){  	int f=ask(1,1,sz,pos[i]);  	if (f==t[0]) printf("-1 ");  	else printf("%d ",f-dis[i]);  }}int main(){  scanf("%d%d",&n,&m);memset(t,127,sizeof(t));memset(p,127,sizeof(p));  for (int i=1;i<=m;i++){    scanf("%d%d%d%d",&x,&y,&w,&f);    if (!f) b[++num].st=x,b[num].en=y,b[num].w=w;    else add(x,y,w),add(y,x,w);  }	  dfs(1),dfs2(1,1);solve();}