#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <bitset>
#define NMAX 50005
#define DMAX 0xfffffff

using namespace std;

void read(),solve(),write();

typedef pair<unsigned int,unsigned int> pereche;
typedef list<pereche> lista;

struct cmp
{
	bool operator()(const pereche &a, const pereche &b)
	const
	{
		return a.second>b.second;
	}
};

lista G[NMAX];
vector<unsigned int> dist(NMAX,DMAX);
priority_queue<pereche,vector<pereche>,cmp>coada;
bitset<NMAX> verificat(0);

int N,M;

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	read();
	solve();
	write();
	
	return 0;
}

void write()
{
	for(int i=2;i<=N;i++)
		cout<<nounitbuf<<(dist[i]!=DMAX?dist[i]:0)<<" ";
}

void solve()
{
	dist[1]=0;
	coada.push(pereche(1,0));
	
	while(!coada.empty())
	{
		pereche nod=coada.top();
		coada.pop();
		if(!verificat[nod.first])
		{
			for(lista::iterator it=G[nod.first].begin();it!=G[nod.first].end();it++)
				if(dist[(*it).first]>nod.second+(*it).second)
				{
					dist[(*it).first]=nod.second+(*it).second;
					coada.push(pereche((*it).first,dist[(*it).first]));
				}
			verificat[nod.first]=true;
		}
	}
}

void read()
{
	scanf("%d %d", &N, &M);
	for(int i=0;i<M;i++)
	{
		int s,d,c;
		scanf("%d %d %d", &s, &d, &c);
		G[s].push_back(pereche(d,c));
	}
}