//Include
#include <fstream>
#include <utility>
#include <vector>
#include <queue>
using namespace std;

//Definitii
#define edge pair<int, int>
#define cost first
#define node second

#define pb push_back
#define mp make_pair

//Constante
const int MAX_SIZE = (int)5e4+1;
const int oo = (1<<30) - 1;

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

int nodes, edges;

vector<edge> graph[MAX_SIZE];
vector<edge>::iterator it, end;

vector<int> dist(MAX_SIZE, oo);

priority_queue<edge, vector<edge>, greater<edge> > heap;

//Main
int main()
{
	in >> nodes >> edges;
	int cFrom, cTo, cCost;
	while(edges--)
	{
		in >> cFrom >> cTo >> cCost;
		graph[cFrom].pb(mp(cCost, cTo));
	}
	
	heap.push(mp(0, 1));
	dist[1] = 0;
	
	while(!heap.empty())
	{
		int current = heap.top().node;
		heap.pop();
		
		end = graph[current].end();
		it = graph[current].begin();
		for(; it!=end ; ++it)
		{
			if(dist[current] + it->cost < dist[it->node])
			{
				dist[it->node] = dist[current] + it->cost;
				heap.push(mp(dist[it->node], it->node));
			}
		}
	}
	
	for(int i=2 ; i<=nodes ; ++i)
		out << (dist[i]==oo? 0 : dist[i]) << ' ';
	
	
	in.close();
	out.close();
	return 0;
}