#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define NMAX 50005
#define INF 1<<25
int n, m;
struct Punct { int c; int urm; } nod;
vector<Punct> matrice[NMAX];
vector<int> d(NMAX, INF);
short viz[NMAX];
void citire() 
{   f>>n>>m;
	int x;
	for(register int i=1; i<=m; i++) {
		f>>x>>nod.urm>>nod.c;
		matrice[x].push_back(nod);
	}
	f.close();
}
void dijkstra() 
{   int x=0;
    short start = 1; d[start] = 0;
	queue <int> Q; Q.push(start);
	viz[start] =1;
	while(!Q.empty())
	{   x=Q.front(); Q.pop();
		viz[x]=0;
		vector<Punct> :: iterator it;
		for(it=matrice[x].begin(); it!=matrice[x].end();++it)
		  if(d[x] + it->c < d[it->urm]) 
			    {
				d[it->urm] = d[x] + it->c;
				if(!viz[it->urm]) Q.push(it->urm);
			     }
	}
}

int main() 
{   citire();
	dijkstra();
	for(int i=2; i<=n; i++)
		if(d[i] == INF) g<<"0 ";	
		else g<<d[i]<<' ';
	g.close();
}