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

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 sz = (int) 5e4+1;
const int oo = (1<<30)+1;

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

vector<pii> graph[sz];

int dist[sz];

priority_queue< pii, vector<pii>, greater<pii> > q;

//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, &weight);
		graph[node1].pb(mp(weight,node2));
	}
	
	dist[1] = 0;
	
	for(int i=2; i<=nodes; ++i)
		dist[i] = oo;
	
	q.push(mp(0,1));
	
	while (!q.empty())
	{
		pii current = q.top();
		q.pop();
		
		vector<pii> :: iterator it, end=graph[current.to].end();
		
		for( it=graph[current.to].begin(); it!=end; ++it)
		{
			if( dist[it->to] > current.cost + it->cost)
			{
				dist[it->to] = current.cost + it->cost;
				q.push(mp(current.cost + it->cost, it->to));
			}
		}
	}
	
	for(int i=2; i<=nodes; ++i)
		if(dist[i] == oo)
			fprintf(out,"0 ");
		else 
			fprintf(out,"%d ", dist[i]);
		
	
	fclose(in);
	fclose(out);
	return 0;
}