#include<fstream> 
#include<vector>
#include<queue>
#define inf 0xfffffff
using namespace std; 

ifstream in("dijkstra.in"); 
ofstream out("dijkstra.out"); 

int N,M,d[50001];

struct nod
{
	int y,c; 
};
vector<nod> V[50001]; 

queue<int> coada ;

void Read() 
{
	in >> N >> M; 
	int x; 
	nod t; 
	for(int i = 1; i <= M; i++) 
		{
			in >> x >> t.y >> t.c; 
			V[x].push_back(t); 
	}
}

void Dijkstra() 
{
	for(int i = 2; i <= N; i++) 
			d[i]=inf; 
	d[1]=0; 
	coada.push(1); 
	
	while(!coada.empty()) 
	{
		int x=coada.front(); 
		
			for(int i = 0; i < V[x].size(); i++) 
			{
				int y = V[x][i].y; 
				int c = V[x][i].c; 
				if(d[y] > d[x]+c) 
					{
						d[y] = d[x]+c;
				coada.push(y);
				}				
			}
		
		coada.pop(); 
	}
}

int main() 
{
	Read(); 
	Dijkstra(); 
	
	for(int i = 2; i <= N; i++) 
		if(d[i]!=inf) 
			out<<d[i]<<" "; 
		else out<<"0 "; 
		
}