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

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

#define mp make_pair
#define pb push_back

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

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

int nodes, edges;
int dist[sz];

vector<pii> graph[sz];
priority_queue< pii, vector<pii>, greater<pii> > pq;

// Main
int main()
{
	in >> nodes >> edges;
	
	for(int i=2 ; i<=nodes ; ++i)
		dist[i] = oo;
	
	int rFrom, rTo, rCost;
	while(edges--)
	{
		in >> rFrom >> rTo >> rCost;
		graph[rFrom].pb(mp(rCost, rTo));
	}
	
	pq.push(mp(0, 1));
	
	while(!pq.empty())
	{
		int currentNode = pq.top().node;
		pq.pop();
		
		vector<pii>::iterator it, end=graph[currentNode].end();
		
		for(it=graph[currentNode].begin() ; it!=end ; ++it)
		{
			if(dist[currentNode] + it->cost < dist[it->node])
			{
				dist[it->node] = dist[currentNode] + it->cost;
				pq.push(mp(dist[it->node], it->node));
			}
		}
	}
	
	for(int i=2 ; i<=nodes ; ++i)
		out << (dist[i]!=oo? dist[i] : 0) << ' ';
	out << '\n';
	
	in.close();
	out.close();
	return 0;
}