#include<iostream>
using namespace std;
const int oo = 0x3fffffff; // 0x7fffffff:  int类型的最大值 
const int N = 10000;
int n,m;//n个顶点，m条边

struct edge{
	int to,w,next;
}e[10005];

bool color[N+5];
int dist[N+5];
int pred[N+5];

int vex[N+5];
int cnt = 0; //cnt:边的编号 
void addedge(int u,int v,int w){
	++cnt;
	e[cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = vex[u];
	vex[u] = cnt;
}

// 迪杰斯特拉算法 
void dijkstra(int s){
	dist[s] = 0;//s到s的距离为0	
	for( int i=1;i<=n ;i++ ){
		//找到白点中距离源点s的最短的顶点rec
		int minDist = oo, rec = 0;
		for( int j=1;j<=n;j++ ){
			if( color[j] == 0 && dist[j] < minDist  ){
				minDist = dist[j];
				rec = j;
			}
		} 
		//通过顶点rec 去更新与其相邻的顶点
		for( int index = vex[rec] ; index!=0 ; index = e[index].next ){
			edge tmp = e[index];//tmp：和rec相连的边 
			int to = tmp.to;
			int w = tmp.w; 
			if( dist[rec] + w < dist[to] ){
				dist[to] = dist[rec] + w;
				pred[to] = rec;
			}
		} 
		color[rec] = 1;//标记黑点 
	} 
} 

int main(){
	cin>>n>>m;
	//初始化
	for(int i=1;i<=n;i++){
		color[i] = 0;
		dist[i] = oo;
		pred[i] = 0;
	} 
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		addedge( u,v,w );//单相边
		// addedge( v,u,w )  反向边  
	}
	
	int s = 1;//源点 
	//调用函数 
	dijkstra(s);
	for( int i=1;i<=n;i++){
		cout<< dist[i] << ' ';
	} 
	return 0 ;
}
/*
5 9
1 2 8
1 4 5
2 4 2
2 3 1
3 5 4
4 2 3
4 3 9
4 5 2
5 3 6
*/