#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>

using namespace std;

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define IT vector< pair<int,int> >:: iterator


const int MAXN = 50005;
const int INF = 0x3f3f3f3f;

vector< pair<int,int> > G[MAXN];

int M, N;
int Dmin[MAXN];

//bellman
void Solve()
{
     bool InQueue[MAXN];
     queue<int> Q;

     memset(Dmin,INF,sizeof(Dmin));
     memset(InQueue, false, sizeof(InQueue));

     Dmin[1] = 0;
     Q.push(1);
     InQueue[1] = true;

     while(!Q.empty()){
     	int nod = Q.front();
	Q.pop();
	InQueue[nod]  = false;

	for(IT it = G[nod].begin(); it != G[nod].end();++it)
	   if(Dmin[nod] + it->second < Dmin[it->first]) 
	   {
	   	Dmin[it->first] = Dmin[nod] + it->second;
		if(!InQueue[it->first]){
		   Q.push(it->first);
		   InQueue[it->first] = true;
		}
	   }
     }
	
}

void ReadInputs()
{
	ifstream fin(FIN);
	int a,b,c;
	fin >> N >> M;
	cout << N << " - " << M;
	for(int i = 0; i < M; ++i){
		fin >> a >> b >> c;
		G[a].push_back(make_pair(b,c));
	}

}

void WriteOutputs()
{
	ofstream fout(FOUT);
	for(int i = 2; i <= N; ++i)
		fout << ((Dmin[i] < INF)?Dmin[i]:0) << " ";
}


int main()
{
	ReadInputs();
	Solve();
	WriteOutputs();
	return 0;

}