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

#define N 50005
#define pinf 5000030000
using namespace std;

long long D[N];

struct Nod{
  int nod,cost;
};

class Compar  //vezi priority_queue.pdf
{
 public:
 bool operator()( Nod x, Nod y)
 {
    if(x.cost>y.cost) return true; // ordine crscatoare
    else return false;
 }
};

priority_queue< Nod, vector< Nod >, Compar > coada;

int n,m;;

vector <vector< Nod > >L(N);

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void dijkstra(int r)
{
    int i,poz,c;
    Nod a;

    for(i=1;i<=n;i++)
      D[i]=pinf;

    a.nod=r;a.cost=0;
    coada.push(a);D[r]=0;

    while(!coada.empty())
    {

        poz=coada.top().nod;  //extragem din coada nodul poz si costul c,
        c=coada.top().cost;    //cu care a fost pus poz in coada
        coada.pop();

        if(D[poz]==c)  //daca poz e la distanta minima fata de sursa
        {
          //parcurgem lista de adiacenta a lui poz
          for(i=0;i<L[poz].size();i++)
            if(D[L[poz][i].nod]>D[poz]+L[poz][i].cost ) //daca putem imbunatati distanta
            {
                D[L[poz][i].nod]=D[poz]+L[poz][i].cost;
                a.cost=D[L[poz][i].nod];a.nod= L[poz][i].nod;
                coada.push(a);
                   //adaugam nodul si distanta imbunatatita in coada
            }
        }
    }

}

int main()
{
   int x,y,c,i;
   Nod a;
   f>>n>>m;
   for(i=1;i<=m;i++)
   {
      f>>x>>y>>c;
      a.cost=c;a.nod=y;
      L[x].push_back(a);
   }

   dijkstra(1);
   for(i=2;i<=n;i++)
     if(D[i]!=pinf) g<<D[i]<<" ";
     else g<<0<<" ";

   f.close();
   g.close();
   return 0;
}