#include<fstream>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
#define nmax 50005
#define pb push_back
#define inf 1<<30
vector<int> g[nmax],c[nmax];
int viz[nmax],d[nmax];
int n,m,s=1;

struct comp
{
	bool operator()(int i,int j)
	{
		return d[i]>d[j];
	}
};

void dijkstra(int nod)
{
	int i,k;
	priority_queue<int,vector<int>,comp> q;
	for(i=1;i<=n;i++)
		d[i]=inf;
	q.push(nod);
	d[nod]=0;
	while(!q.empty())
	{
		k=q.top();
		viz[k]=0;
		q.pop();
		for(i=0;i<g[k].size();i++)
			if(d[g[k][i]]>d[k]+c[k][i])
			{
				d[g[k][i]]=d[k]+c[k][i];
				if(viz[g[k][i]]!=1)
					q.push(g[k][i]),viz[g[k][i]]=1;
			}
	}
}

int main ()
{
	FILE *fin;
	fin=fopen("dijkstra.in","r");
	int i,a,b,cost;
	fscanf(fin,"%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		fscanf(fin,"%d%d%d",&a,&b,&cost);
		g[a].pb(b);
		c[a].pb(cost);
	}
	fclose(fin);
	
	dijkstra(s);
	
	ofstream fout("dijkstra.out");
	for(i=2;i<=n;i++)
		if(d[i]==inf) fout<<0<<' ';
		else fout<<d[i]<<' ';
	fout.close();
	return 0;
}