#include<fstream>
#include<vector>
#include<list>
#include<stack>

#define NMAX 100005

using namespace std;

long n,m,vizitat[NMAX];
stack<long> S;

long long d[NMAX];

struct nod
{
	long varf;
	long cost;
	nod(){}
	nod(long nvarf,long ncost) : varf(nvarf), cost(ncost){}
};

vector<list<nod> > G;

void dfs(long x)
{
	list<nod>::iterator itr;
	for(itr=G[x].begin(); itr!=G[x].end(); itr++)
	{
		if(vizitat[(*itr).varf]==0)
		{
			vizitat[(*itr).varf]=1;
			dfs((*itr).varf);
		}
	}
	S.push(x);
}

void topologicalSort()
{

	long i;
	for(i=1;i<=n;i++)
		if(vizitat[i]==0)
		{	
			vizitat[i]=1;
			dfs(i);
		}
}

int main()
{
	fstream fin,fout;
	long i,x,y,c;

	fin.open("dijkstra.in",ios::in);
	fout.open("dijkstra.out",ios::out);
	list<nod> lista;

	fin>>n>>m;
	for(i=0;i<=n;i++)
	{
		G.push_back(lista);
		d[i]=LONG_MAX;
	}

	for(i=0;i<m;i++)
	{
		fin>>x>>y>>c;
		G[x].push_back(nod(y,c));
	}

	topologicalSort();
	d[1]=0;
	while(!S.empty())
	{
		long varf=S.top();
		S.pop();
		list<nod>::iterator itr;
		for(itr=G[varf].begin(); itr!=G[varf].end(); itr++)
			if(d[(*itr).varf]>d[varf]+(*itr).cost)
			{
				d[(*itr).varf]=d[varf]+(*itr).cost;
			}		
	}
	for(i=2;i<=n;i++)
		if(d[i]==LONG_MAX)
			fout<<"0 ";
		else fout<<d[i]<<" ";

	fin.close();
	fout.close();
	return 0;
}