#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
#include<cstdlib>
using namespace std;

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

struct Edge
{
    int nod;
    short cost;
};

int N, M;
int viz[50009];
int d[50009];
vector <Edge> L[50009];

void Citire()
{
   int x, y, cost;
   Edge w;
   fin >> N >> M;
   for (int i = 0; i < M; i++)
   {
	fin >> x >> y >> cost;
	w.nod = y;
	w.cost = cost;
	L[x].push_back(w);
   }
}

void Rezolva()
{
   int nod, next_node, cost, j;
   queue <int> q;
   q.push(1);

   while(!q.empty())
   {
	    nod = q.front();

	for (j = 0; j < L[nod].size(); j++)
	{
	     next_node = L[nod][j].nod; cost = L[nod][j].cost;
	     if (!viz[next_node] || (d[next_node] > d[nod] + cost))
	     {
		 viz[next_node]++;
		 q.push(next_node);
		 d[next_node] = d[nod] + cost;
	     }
	}

	q.pop();
   }
}

void Afisare()
{
   int i, j;
   for (i = 2; i <= N; i++)
   {
	fout << d[i] << " ";
   }
   fout << endl;
}


int main ()
{
  Citire();
  Rezolva();
  Afisare();
  return 0;
}