#include<fstream>
#include<queue>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,a,b,c,i,cul[50005],cost[50005];

struct node
{
	int nr,c;
	node *next;
}	*v[50005],*p;

queue<int> q;

void dijkstra(int s)
{
	int w;
	q.push(s);
	while(!q.empty())
	{
		w=q.front();
		q.pop();
		cul[w]=2;
		p=v[w];
		while(p)
		{
			if(!cul[p->nr] || (cul[p->nr]==2 && cost[p->nr]>cost[w]+p->c))
			{
				cul[p->nr]=1;
				q.push(p->nr);
				cost[p->nr]=cost[w]+p->c;
			}
			else if(cost[p->nr]>cost[w]+p->c)	cost[p->nr]=cost[w]+p->c;
			p=p->next;
		}
	}
}


int main()
{
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>a>>b>>c;
		p=new node;
		p->nr=b;
		p->c=c;
		p->next=v[a];
		v[a]=p;
	}
	dijkstra(1);
	for(i=2;i<=n;i++) g<<cost[i]<<' ';
	g<<'\n';
	
	f.close();
	g.close();
	return 0;
}