#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

struct nodeDistPair{
	int node,dist;
	nodeDistPair(int n,int d){
		node=n;dist=d;
	}
};


bool operator<(nodeDistPair n1,nodeDistPair n2){return n1.dist<n2.dist;}
bool operator>(nodeDistPair n1,nodeDistPair n2){return n1.dist>n2.dist;}
int dist[50004];
vector< vector< pair<int,int> > > G(50004);
//vector< vector<int> > C(50004);


int main(){

	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	priority_queue <nodeDistPair,vector<nodeDistPair>,less<nodeDistPair> > pq;
	int n,m,x,y,c;
	scanf("%d",&n);
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d",&x);scanf("%d",&y);scanf("%d",&c);
		G[x].push_back(pair<int,int>(y,c));
	}
	for(int i=1;i<=n;i++){dist[i]=50000006;}
	dist[1]=0;
	nodeDistPair first(1,0); pq.push(first);
	
	
	while(!pq.empty()){
		nodeDistPair u = pq.top();pq.pop();
		if(dist[u.node]!=u.dist) continue;
		for(int i=0;i<G[u.node].size();i++){
			int v=G[u.node][i].first;
			if(dist[v]>dist[u.node]+G[u.node][i].second){
				nodeDistPair newN(v,dist[u.node]+G[u.node][i].second);
				dist[v]=newN.dist;	
				pq.push(newN);
			}
		}
	}
	
	for(int i=2;i<=n;i++) printf("%d ",dist[i]);
	printf("\n%d\n",(-3%4));
	return 0;
}