#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#define MAXN 50004
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;

struct XYZ{
  int node,cost;
};
struct ABC{
  int neigh,cost;
};

vector <ABC> graf[MAXN];
queue <XYZ> q;
int cost[MAXN];
int seen[MAXN];

void DFS(XYZ node){
  cost[node.node]=0;
  seen[node.node]=1;
  q.push(node);
  while(!q.empty()){
    node=q.front();
    q.pop();
    for(ABC neigh : graf[node.node]){
      if(seen[neigh.neigh]==0 || cost[neigh.neigh]>cost[node.node]+neigh.cost){
        cost[neigh.neigh]=cost[node.node]+neigh.cost;
        seen[neigh.neigh]=1;
        q.push({neigh.neigh,cost[neigh.neigh]});
      }
    }
  }
}

int main(){
  int n,m,x,y,z,i;
  FILE *fin,*fout;
  fin=fopen("dijkstra.in","r");
  fout=fopen("dijkstra.out","w");
  fscanf(fin,"%d%d",&n,&m);

  for(i=0;i<m;i++){
    fscanf(fin,"%d%d%d",&x,&y,&z);
    graf[x].push_back({y,z});
  }

  DFS({1,0});

  for(i=2;i<=n;i++){
    fprintf(fout,"%d ",cost[i]);
  }
  fprintf(fout,"\n");

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