记录编号	168096	评测结果	AAAAAAAAAA
题目名称	龙凡	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.508 s
提交时间	2015-07-01 07:53:39	内存使用	20.63 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=100010,SIZEM=400010;
const int INF=0x7fffffff/2;
class Edge{
public:
	int u,v;
	int len;
	int sum;//两端的depth之和加上len
};
class Node{//小根堆左偏树的节点
public:
	int l,r;
	int h;
	Edge e;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define h(x) tree[x].h
	#define e(x) tree[x].e
};
Node tree[SIZEM];
int node_merge(int u,int v){
	if(!u||!v) return u+v;
	if(e(u).sum>e(v).sum) swap(u,v);
	r(u)=node_merge(r(u),v);
	if(h(l(u))<h(r(u))) swap(l(u),r(u));
	h(u)=h(r(u))+1;
	return u;
}
int ufs[SIZEN]={0};
int grand(int x){
	return !ufs[x]?x:ufs[x]=grand(ufs[x]);
}
int N,M;
Edge edges[SIZEM];int tot=0;
vector<int> c[SIZEN];
int depth[SIZEN]={0};
int father[SIZEN]={0};
int ans[SIZEN]={0};
int root[SIZEN]={0};
int vis[SIZEN]={0};
void DFS(int x){
	if(vis[x]) return;
	vis[x]=true;
	for(int i=0;i<c[x].size();i++){
		Edge &eg=edges[c[x][i]];
		if(depth[x]+eg.len==depth[eg.v]){
			if(vis[eg.v]) continue;
			father[eg.v]=x;
			DFS(eg.v);
			root[x]=node_merge(root[x],root[eg.v]);
			ufs[grand(eg.v)]=grand(x);
		}
	}
	for(int i=0;i<c[x].size();i++){
		Edge &eg=edges[c[x][i]];
		if(grand(eg.v)!=x&&eg.v!=father[x]){
			root[x]=node_merge(root[x],c[x][i]);
		}
	}
	//现在,root[x]中压入了所有可能合法的边
	while(root[x]&&grand(e(root[x]).v)==x){
		root[x]=node_merge(l(root[x]),r(root[x]));
	}
	if(root[x]) ans[x]=e(root[x]).sum-depth[x];
	else ans[x]=-1;
}
void work(void){
	for(int i=1;i<=2*M;i++){
		e(i)=edges[i];
		e(i).sum=depth[e(i).u]+depth[e(i).v]+e(i).len;
	}
	DFS(1);
	for(int i=2;i<=N;i++) printf("%d\n",ans[i]);
}
priority_queue<pair<int,int> > Q;
bool used[SIZEN];
void Dijkstra(int s){
	for(int i=1;i<=N;i++) depth[i]=INF;
	depth[s]=0;Q.push(make_pair(-depth[s],s));
	while(!Q.empty()){
		int x=Q.top().second;Q.pop();
		if(used[x]) continue;
		used[x]=true;
		for(int i=0;i<c[x].size();i++){
			Edge &eg=edges[c[x][i]];
			if(depth[x]+eg.len<depth[eg.v]){
				depth[eg.v]=depth[x]+eg.len;
				Q.push(make_pair(-depth[eg.v],eg.v));
			}
		}
	}
}
void add_edge(int a,int b,int w){
	edges[++tot]=(Edge){a,b,w,0};
	c[a].push_back(tot);
}
void read(void){
	scanf("%d%d",&N,&M);
	int a,b,w;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&a,&b,&w);
		add_edge(a,b,w);
		add_edge(b,a,w);
	}
}
int main(){
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	read();
	Dijkstra(1);
	work();
	return 0;
}