#include<stdio.h>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>


using namespace std;

FILE *in,*out;

//definitions
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define cost first
#define to second


//constants
const int oo = (1<<30)-1;
const int sz = (int) 5e4+1;

//variables
int nodes, edges;
int node1, node2, costs;

vector<pii> graph[sz];

priority_queue< pii, vector<pii>, greater<pii> > q;
 
int dist[sz];

//functions

int main(void)
{
	in = fopen( "dijkstra.in", "rt");
	out = fopen( "dijkstra.out", "wt");
	
	fscanf(in, "%d%d", &nodes,&edges);
	
	while(edges--)
	{
		fscanf(in, "%d%d%d", &node1, &node2, &costs);
		graph[node1].pb(mp(costs,node2));
	}
	
	dist[1] = 0;
	
	for(int i=2; i<=nodes; ++i)
		dist[i] = (1<<30)-1;
	
	q.push(mp(0,1));
	
	while(!q.empty())
	{
		pii curent = q.top();
		q.pop();
		
		vector<pii> :: iterator it,end = graph[curent.to].end();
		
		for( it=graph[curent.to].begin(); it!=end; ++it)
		{
			if(dist[it->to] > it->cost + curent.cost )
			{
				dist[it->to] = it->cost + curent.cost;
				q.push(mp(it->cost + curent.cost,it->to));
			}
		}
	}
	
	for(int i=2; i<=nodes; ++i)
	{
		if(dist[i] == (1<<30)-1)
			fprintf(out,"0 ");
		else
			fprintf(out, "%d ", dist[i]);
	
	fclose(in);
	fclose(out);
	return 0;
}