#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<int> > G(50004);
vector< vector<int> > C(50004); 

int main(){
	const int INF=50000006;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	priority_queue <nodeDistPair,vector<nodeDistPair>,greater<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(y);C[x].push_back(c);
	}
	for(int i=1;i<=n;i++){dist[i]=INF;}
	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];
	if(dist[v]>dist[u.node]+C[u.node][i]){
	nodeDistPair newN(v,dist[u.node]+C[u.node][i]);
	dist[v]=newN.dist; 
	pq.push(newN);
	}
	}
	}
 
	for(int i=2;i<=n;i++) printf("%d ",(dist[i]!=INF?dist[i]:0));
 
	return 0;
}