#include<fstream>
#include<queue>
#include<vector>
using namespace std;
#define inf 1000000000
#define nmax 50005
#define pb push_back
typedef vector<int> VI;
VI c[nmax],g[nmax];
int n,s=1,m,d[nmax],viz[nmax];
void citire ()
{
	ifstream fin("dijkstra.in");
	
	fin>>n>>m;
	int i,a,b,cost;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b>>cost;
		g[a].pb(b);c[a].pb(cost);
	}
	fin.close();
}
struct comp
{
	bool operator()(int i,int j)
{
	return d[i]>d[j];
	}
};
priority_queue<int> q;
void dijkstra(int nod)
{
	int k,i;
	for(i=1;i<=n;i++)
		d[i]=inf;
	d[nod]=0;
	q.push(nod);
	while(!q.empty())
	{
		k=q.top();
		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];
				q.push(g[k][i]);
				
			}
	}
}
void dijkstra2(int nod)
{
	int q2[1<<20];
	int i,k,inc=0,sf=0;
	for(i=1;i<=n;i++)
		d[i]=inf;
	q2[inc=sf=0]=nod,d[nod]=0;
	while(inc<=sf)
	{
		k=q2[inc++];
		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],q2[++sf]=g[k][i];
	}
}
void scrie()
{
	ofstream fout("dijkstra.out");
	int i;
	for(i=2;i<=n;i++)
		if(d[i]==inf) fout<<0<<' ';
		else fout<<d[i]<<' ';
	fout.close();
}
int main()
{
	citire();
	dijkstra(s);
	scrie();
	return 0;
}