#include<fstream>
#include<queue>
#include<algorithm>
#define maxn 50001
#define inf 0x3f3f3f3f
#define infile "dijkstra.in"
#define outfile "dijkstra.out"

using namespace std;

ifstream in(infile);
ofstream out(outfile);



struct graf
{
	int nod,cost;
	graf *next;
};

graf *a[maxn];
int d[maxn],n,m;
queue<int> h;
bool inqueue[maxn];

void read()
{
	int x,b,c;
	in>>n>>m;
	for(int i=1;i<=m;i++)
	{		
		in>>x>>b>>c;
		graf *q=new graf;
		q->nod=b;
		q->cost=c;
		q->next=a[x];
		a[x]=q;		
	}
}


void solve()
{
	for(int i=1;i<=n;i++)
	{
		d[i]=inf;
		inqueue[i]=false;
	}
	d[1]=0;
	h.push(1);
	inqueue[1]=true;
	while(!h.empty())
	{
		int min=h.front();
		h.pop();
		inqueue[min]=false;
		graf *q=a[min];
		while(q)
		{
			if(d[q->nod]>d[min]+q->cost)
			{
				d[q->nod]=d[min]+q->cost;
			if(inqueue[q->nod]==false)
			{
				h.push(q->nod);
				inqueue[q->nod]=true;
			}
			}
			q=q->next;
		}
	}
}

int main()
{
	read();
	solve();
	for(int i=2;i<=n;i++)
	{
		if(d[i]==inf)
			out<<"0"<<" ";
		else
		out<<d[i]<<" ";
	}
	return 0;
}