#include<fstream>
#include<queue>
using namespace std;
#define nmax 50005
#define pb push_back
#define inf 1<<20
vector< pair<int,int> > g[nmax];
priority_queue<int> q;
int d[nmax],viz[nmax];
int n,m;
void citire ()
{
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	int i,a,b,c;
	for(i=1;i<=m;i++)
		fin>>a>>b>>c,g[a].pb(make_pair(b,c));
	fin.close();
}
void dijkstra (int nod)
{
	int i,x;
	for(i=1;i<=n;i++)
		d[i]=inf;
	q.push(nod);
	d[nod]=0;
	while(q.size()!=0)
	{
		x=q.top();viz[x]=0;
		q.pop();
		for(i=0;i<g[x].size();i++)
			if(d[g[x][i].first]>d[x]+g[x][i].second )
			{
				
				d[g[x][i].first]=d[x]+g[x][i].second;
				if(viz[g[x][i].first]!=1 )
				viz[g[x][i].first]=1,q.push(g[x][i].first);
			}
	}
}
void scrie()
{
	int i;
	ofstream fout("dijkstra.out");
	for(i=2;i<=n;i++)
		if(d[i]==inf) fout<<0<<' ';
		else fout<<d[i]<<' ';
	fout.close();
}
int main ()
{
	citire();
	dijkstra(1);
	scrie();
	return 0;
}