//100% working
#include<fstream>
#include <vector>
#include <queue>

#define NMAX 50005
#define INF 0x3f3f3f3f
using namespace std;

vector<pair<int, int> > G[NMAX];
int d[NMAX];
queue <int> Q;
int N;
bool is[NMAX];


inline void init()
{	
	int i;
	memset(d,INF,sizeof(d));
	memset(is, false, sizeof(is));
	d[1]=0;
	Q.push(1);
	is[1]=1;
}

inline void citire()
{
	int M;
	ifstream fin("dijkstra.in");
	fin>>N>>M;
	int x,y,c;
	for(int i=1;i<=M;i++)
		{
			fin>>x>>y>>c;
			G[x].push_back(make_pair(y, c));
		}
	fin.close();
}

inline void afisare()
{
	ofstream fout("dijkstra.out");
	for(int i=2;i<=N;i++)
		if(d[i]==INF) fout<<"0 ";
	else 
		fout<<d[i]<<" ";
	fout<<"\n";
	fout.close();
}

inline void bell()
{
	int x;
	unsigned int i;
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		is[x]= false;
		for(vector< pair<int, int> >::iterator it = G[x].begin(); it != G[x].end(); ++it)
		{ 
			if(d[x] + it -> second < d[it->first])
			{
				d[it->first]=d[x]+it->second;
				if(is[it->first] == false)
				{
					Q.push(it->first);
					is[it->first]= true;
				}
			}
		}
	}
}

int main()
{
	
	citire();
	init ();
	
	bell();
	
	afisare();
}