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

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
	
	
const int N=50004;
const int inf=0x3f3f3f3f;

int dist[N],n;
bool use[N];

struct Nod
{
	int x,cost;
	Nod(int _x,int _cost)
	{
		x=_x;
		cost=_cost;
	}
	Nod()
	{
		x=0;
		cost=0;
	}
	bool operator< (const Nod &x) const
	{
		return cost>x.cost;
	}
};

vector <Nod> v[N];

void dijkstra (int start)
{
	memset(use, false, sizeof(use));
	memset(dist, inf, sizeof(dist));
	int x,y,c;
	dist[start]=0;
	
	priority_queue <Nod> h;
	
	h.push(Nod(start,dist[start]));
	
	while(!h.empty())
	{
		x=h.top().x;
		h.pop();
		if(use[x])
			continue;
		use[x]=true;
		
		for(vector <Nod> :: iterator it= v[x].begin(); it!=v[x].end();it++)
		{
			y=it->x;
			c=it->cost+dist[x];
			if(dist[y]>c)
			{
				dist[y]=c;
				h.push(Nod(y,c));
			}
		}
	}
}
	
	
	

int main()
{
	
	int m,i,x,y,c;
	in>>n>>m;
	
	while(m--)
	{
		in>>x>>y>>c;
		v[x].push_back(Nod(y,c));
	}
	
	dijkstra(1);
	
	for(i=2;i<=n;i++)
	{
		if(dist[i]==inf)
			out<<"0 ";
		else
			out<<dist[i]<<" ";
	}
	
	return 0;
}