#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<vector<int> > graf;
vector<vector<int> > costuri;
vector<int> dist_min;
queue<int> coada;
int n,m;


int main()
{
  f>>n>>m;
  graf.resize(m);
  costuri.resize(m);
  dist_min.resize(n,infinit);
  dist_min[0]=0;
  coada.push(0);
  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 = 1; j<n; j++)
    if(dist_min[j]==infinit)
      g<<"0";
    else g<<dist_min[j]<<" ";

  return 0;
}