#include <fstream>
#include <vector>
#define INF 250001
using namespace std;

int N, M;
vector <vector <int> > C;
vector <int> d;
vector <bool> s;

int main(){
  int i, j, k, dist;

  ifstream fin ("dijkstra.in");
  fin >> N >> M;
  C.resize(N, vector <int>(N, INF));
  s.resize(N);
  d.resize(N);
  for (k=0; k<M; k++){
    fin >> i >> j >> dist;
    i--; j--;
    C[i][j]=dist;
  }
  fin.close();

  for (i=1; i<N; i++)
    d[i]=C[0][i];
  d[0]=0;
  s[0]=true;
  for (k=0; k<N-1; k++){
    dist=INF;
    for (j=0; j<N; j++)
      if (dist>d[j] && s[j]==false){
        i=j;
        dist=d[j];
      }
    s[i]=true;
    for (j=0; j<N; j++)
      if (d[j]>d[i]+C[i][j])
        d[j]=d[i]+C[i][j];
  }

  ofstream fout ("dijkstra.out");
  for (i=1; i<N; i++)
    if (d[i]==INF)
      fout << "0 ";
    else
      fout << d[i] << ' ';
  fout << '\n';
  fout.close();

  return 0;
}