#include<stdio.h>
#include<vector>
#include<queue>
#define INF 2000000000
using namespace std;
struct Graf{
  int node,lung;
};
struct Que {
  int node,lung;
  bool operator < (const Que &other)const{
    return lung > other.lung;
  }
};

priority_queue <Que> heap;
vector <Graf> v[50005];
int dist[50005];

int main (){
  FILE *in,*out;
  in = fopen ("dijkstra.in","r");
  out = fopen ("dijkstra.out","w");
  int n,m,i,l,n1,n2,nod;
  fscanf(in,"%d%d",&n,&m);/// n noduri & m arce
  for (i=1;i<=m;i++){
    fscanf (in,"%d%d%d",&n1,&n2,&l);///lung de la npd1 la nod2
    v[n1].push_back({n2,l});
  }

  heap.push ({1,0});/// nodul sursa
  for (i=1;i<=n;i++)
    dist[i] = INF;/// dist de la sursa la nodi
  dist[1] = 0;/// dist de la nod sursa la el insusi

  while (heap.empty() == 0){// cat timp coada nu e goala
    nod = heap.top().node; l = heap.top().lung;
    heap.pop();
    if (l == dist[nod])
      for (i = 0; i < v[nod].size(); i++){
        ///v[nod][i]
        l = dist[nod] + v[nod][i].lung;
        if (l < dist[v[nod][i].node]){
          dist[v[nod][i].node] = l;
          heap.push({v[nod][i].node,l});/// node & dist
        }
      }
  }

  for (i=2;i<=n;i++){
    if (dist[i] == INF)
      fprintf(out,"0 ");
    else
      fprintf(out,"%d ",dist[i]);
  }

  fclose (in);
  fclose (out);
  return 0;
}