#include<iostream>
#include<fstream>
#define DN 999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod
{
	int c; int nd; 
	nod *urm;
};
nod *a[100], *p;
int d[250005];

void creare(int x, int y, int cost)
{
	nod *q=new nod;
	q->nd=y;
	q->urm=a[x];
	q->c=cost;
	a[x]=q;
}

int main()
{
	int n, m,x,y,z, i;
	fin>>n>>m;
	for(i=2;i<=n;i++)
		d[i]=DN;
	for(i=1;i<=m;i++)
	{	
		fin>>x>>y>>z; 
		creare(x,y,z);
		if(x==1)
			d[y]=z;
	}
	
	

	for(i=1;i<=n;i++)
	{
		p=a[i];
		while(p)
		{	
			if(d[p->nd]>d[i]+p->c)
				d[p->nd]=d[i]+p->c;
			p=p->urm;
		}
	}
	
	for(i=2;i<=n;i++)
		if(d[i]!=DN)
			fout<<d[i]<<" ";
		else
			fout<<0<<" ";
}