#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits.h>
#include <set>
#define inf INT_MAX-10
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int D[50005], n , m;
vector < pair <int, int> > L[50005];

set < pair <int, int> > h;

//priority_queue <pair <int, int > > Q;

void Citire()
{int i,x,y,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }
}

void Dijkstra()
{int i, j, Start,c,k,ct,  nd ;
    Start=1;
    for(i=1;i<=n;i++)
       if(i!=Start) {D[i]=inf; }


  D[Start]=0;

  h.insert(make_pair(Start, 0));
  while(!h.empty())
  {
      nd = h.begin()->first;
      ct = h.begin()->second;
    //  cout <<endl<<"I:"<<nd<<"-"<<ct<<endl<<":";
      h.erase(h.begin());

      for(k=0;k<L[nd].size();k++)
      { j=L[nd][k].first;
        c=L[nd][k].second;
      //  cout <<j<<"-"<<c<<"/";
        if(D[j]>D[nd]+c)
        {   //if (D[j]!= inf)
             //       h.erase(h.find(make_pair(j, D[j])));

            D[j]=D[nd]+c;
            //Q.push(make_pair(-D[j],j));
            h.insert(make_pair(j, D[j]));
            //Q.emplace(make_pair(-D[j],j));
        }
      }
  }
}
int main()
{ int i;
Citire();
Dijkstra();
for(i=2;i<=n;i++)
    if(D[i]!=inf)
    g<<D[i]<<" ";
    else g<<0<<" ";
g<<endl;
f.close();
g.close();
    return 0;
}