#include <stdio.h>

using namespace std;

#include <vector>
#include <queue>
#define NMAX 50000
#define MMAX 250000
#define INF 1e9

struct edge{
  int to;
  long long cost;
  bool operator < (const edge &a) const {
    return cost > a.cost ; ///sort cresc
  }
};

vector <edge> g[NMAX+1];
priority_queue <edge> q;
long long dist[NMAX+1];

void dijkstra (int n,int nod){
  int i;
  for(i=1;i<=n;i++)
    dist[i]=INF;
  for(auto next : g[nod]){
    q.push({next.to,next.cost});
  }
  dist[nod]=0;
  while(!q.empty()){
    edge next=q.top();///next.cost=costul min din q
    q.pop();
    if(dist[next.to]==INF){ ///nu a fost parcurs nodul
      dist[next.to]=next.cost;
      for(auto elem : g[next.to]){
        q.push({elem.to,dist[next.to]+elem.cost});
      }
    }
  }
}

int main()
{
  FILE *fin,*fout;
  fin=fopen("dijkstra.in","r");
  fout=fopen("dijkstra.out","w");

  int n,m,a,b,c,i;
  fscanf(fin,"%d%d",&n,&m);
  for(i=1;i<=m;i++){
    fscanf(fin,"%d%d%d",&a,&b,&c);
    g[a].push_back({b,c});
  }
  dijkstra(n,1);
  for(i=2;i<=n;i++)
    fprintf(fout,"%d ",dist[i]);

  fclose(fin);
  fclose(fout);
  return 0;
}