#include <iostream>
#include<vector>
#include<fstream>
#include<utility>
#include<queue>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int infinit= 0x7fffffff;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<int>  graf[50009];
vector<int> costuri[50009];
int dist_min[50009];
queue<int> coada;
int n,m;


int main()
{
  f>>n>>m;
  //graf.resize(m);
  //costuri.resize(m);
  //dist_min.resize(n,infinit);
  for(int k=2;k<=n;k++)
     dist_min[k]=infinit;
  dist_min[1]=0;
  coada.push(1);
  for (int i=0; i<m; i++)
  {
    int x,y,z;
    f>>x>>y>>z;
  //  x--;
   // y--;
    graf[x].push_back(y);
    costuri[x].push_back(z);
  }
  while(coada.size()>0)
  {
   int aux=coada.front();
    coada.pop();
       for(unsigned int i=0;i<graf[aux].size();i++)
       {
           if((dist_min[aux]+costuri[aux][i])<dist_min[graf[aux][i]])
           {
               coada.push(graf[aux][i]);
               dist_min[graf[aux][i]]=dist_min[aux]+costuri[aux][i];
           }
       }


  }

  for (int j = 2; j<=n; j++)
    if(dist_min[j]==infinit)
      g<<"0";
    else g<<dist_min[j]<<" ";

  return 0;
}