#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

vector <pair <int,int>> v[50001];
int dist[50001], n;
bool viz[50001];

void dijkstra(int x) {
  int i, nod, nod2, cost;
  for(i=1;i<=n;i++)
    dist[i]=1000000001;
  priority_queue <pair <int,int>> dmin;
  dist[x]=0;
  dmin.push({0,x});
  while(dmin.size()>0) {
    nod=dmin.top().second;
    dmin.pop();
    if(viz[nod]==0) {
      viz[nod]=1;
      for(i=0;i<v[nod].size();i++) {
        nod2=v[nod][i].first;
        cost=v[nod][i].second;
        if(dist[nod]+cost<dist[nod2]) {
          dist[nod2]=dist[nod]+cost;
          dmin.push({-dist[nod2],nod2});
        }
      }
    }
  }
}

int main() {
  FILE *fin, *fout;
  int m, x, y, z, i;
  fin=fopen("dijkstra.in","r");
  fout=fopen("dijkstra.out","w");
  fscanf(fin, "%d%d",&n,&m);
  for(i=1;i<=m;i++) {
    fscanf(fin, "%d%d%d",&x,&y,&z);
    v[x].push_back({y,z});
  }
  dijkstra(1);
  for(i=2;i<=n;i++)
    if(dist[i]==1000000001)
      fprintf(fout, "0 ");
    else
      fprintf(fout, "%d ",dist[i]);
  fclose( fin );
  fclose( fout );
  return 0;
}