#include<cstdio>
#include<vector>
#include<queue>
#define pinf (1<<30)
using namespace std;
vector<pair<int,int> >v[50002];
vector<int>dist;
int n,m;

void citire()
{
	FILE *in=fopen("dijkstra.in","r");
	fscanf(in,"%d%d",&n,&m);
	dist.resize(n+1,pinf);
	int i,x,y,z;
	for(i=1;i<=m;++i)
	{
		fscanf(in,"%d%d%d",&x,&y,&z);
		v[x].push_back( make_pair(z,y) );
	}
	fclose(in);
}
void dijkstra(int s)
{
	int i;
	queue<int>Q;
	vector<bool>InQ(n+1,false);
	dist[s]=0;
	Q.push(s);
	InQ[s]=true;
	while(!Q.empty())
	{
		int nod=Q.front(),u=v[nod].size();
		Q.pop();
		InQ[nod]=false;
		for(i=0; i<u;++i)
		{
			if(dist[nod] + v[nod][i].first <dist[v[nod][i].second])
			{
				dist[v[nod][i].second]=dist[nod]+v[nod][i].first;
				if(!InQ[v[nod][i].second])
					Q.push(v[nod][i].second), InQ[v[nod][i].second]=true;
			}
		}
	}

}
void afisare()
{
	FILE *out=fopen("dijkstra.out","w");
	for(vector<int>::iterator it=dist.begin()+2;it!=dist.end();++it)
		if(*it!=pinf)
			fprintf(out,"%d ",*it);
		else
			fprintf(out,"0 ");
	fclose(out);
}
int main()
{
	citire();
	dijkstra(1);
	afisare();
	return 0;
}