#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
#define NMax 100000
using namespace std;

const char IN[]="dijkstra.in",OUT[]="dijkstra.out";

int N,M;

vector< pair<int,int> > v[NMax];
vector<int> dist , heap;
bool inQueue[NMax];

bool cmp(int x,int y)
{
	return dist[x]>dist[y];
}

void Dijkstra()
{
	vector< pair<int,int> >::iterator it;
	int x;

	inQueue[0]=1;
	dist.assign(N,-1);
	dist[0]=0;
	heap.push_back(0);
	
	while (heap.size()>0)
	{
		x=heap[0];
		pop_heap( heap.begin() , heap.end() , cmp ); heap.pop_back();
		
		for ( it = v[x].begin() ; it<v[x].end();++it)
			if ( dist[it->first]==-1 || dist[it->first] > it->second+dist[x])
			{
				dist[it->first] = it->second+dist[x];
				if ( !inQueue[it->first] )
				{
					heap.push_back(it->first);
					push_heap ( heap.begin() , heap.end() , cmp);
					inQueue[it->first]=true;
				}
			}
	}
}

int main()
{
	int i,x,y,c;
	pair < int , int > a;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	for (i=0;i<M;++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		v[x-1].push_back( make_pair(y-1,c));
	}
	fclose(stdin);
	
	Dijkstra();
	
	freopen(OUT,"w",stdout);
	for (i=1;i<N;++i)
		printf("%d ",dist[i]);
	printf("\n");
	fclose(stdout);
	
	return 0;
}