#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);
vector<Punct> :: iterator it;
bool viz[NMAX];
void citire() 
{   f>>n>>m;
	int x;
	for(int i=1; i<=n; i++) {
		f>>x>>nod.urm>>nod.c;
		matrice[x].push_back(nod);
	}
	f.close();
}
void dijkstra() 
{   queue <int> Q;
    int start=1;
	int x=0; d[start] = 0; viz[start] =1; 
	Q.push(start);
	while(!Q.empty())
	{   x=Q.front(); Q.pop(); viz[x] =0;
		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<<"\n";
	g.close();
}