#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#define MAXN 50004
using namespace std;

struct XYZ{
  int node,cost;
};

bool operator<(const XYZ a,const XYZ b){
  return a.cost>b.cost;
}

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

void DFS(XYZ node){
  q.push(node);
  cost[node.node]=1;

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

int main(){
  int n,m,i,a,b,c;
  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",&a,&b,&c);
    graf[a].push_back({b,c});
  }

  DFS({1,0});

  for(i=2;i<=n;i++){
    if(cost[i]>=1){
      fprintf(fout,"%d ",cost[i]-1);
    }else{
      fprintf(fout,"0 ");
    }
  }

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