#include<fstream>
#include<queue>
#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,poz[maxn];
priority_queue<int> h;

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()
{
	int i;
	for(i=2;i<=n;i++)
		d[i]=inf;
	h.push(1);
	while(!h.empty())
	{
		int min=h.top();
		h.pop();
		graf *q=a[min];
		while(q)
		{
			if(d[q->nod]>d[min]+q->cost)
				d[q->nod]=d[min]+q->cost;
			if(poz[q->nod]==0)
			{
			h.push(q->nod);
			poz[q->nod]=1;
			}
			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;
}