#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMax=50002;
const int oo = (1 << 30) ;

int N,M;
int Dis[NMax];
bool In[NMax];
vector <pair <int,int> > a[NMax];

struct comp
{
	bool operator()(int x, int y)
	{
		return Dis[x]>Dis[y];
	}
};

priority_queue <int, vector<int>, comp> coada;

void Citeste()
{
	fin >> N >> M;
	for(int i=1;i<=M;i++)
	{
		int x,y,c;
		fin >> x >> y >> c;
		a[x].push_back(make_pair(y,c));
	}
	for(int i=1;i<=N;i++)
	    Dis[i]=oo;
}
void Dijkstra(int st)
{
	Dis[st]=0;
	coada.push(st);
	In[st]=true;
	while(!coada.empty())
	{
		int Nod=coada.top();
		coada.pop();
		In[Nod]=false;
		for(int i=0;i<a[Nod].size();i++)
		{
			int Vecin=a[Nod][i].first;
			int Cost=a[Nod][i].second;
			if(Dis[Nod]+Cost<Dis[Vecin])
			{
				Dis[Vecin]=Dis[Nod]+Cost;
				if(In[Vecin]==false)
				{
					coada.push(Vecin);
					In[Vecin]=true;
				}
			}
		}
	}
}
void Afiseaza()
{
	for(int i=2;i<=N;i++)
	    if(Dis[i]!=oo)
	        fout << Dis[i] << " ";
	    else
	        fout << 0 << " ";
}
int main()
{
	
	Citeste();
	Dijkstra(1);
	Afiseaza();
	
	return 0;
	
}