#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct edge{
  int dest, cost, d;
};

struct node{
  vector<edge> vec;
};

vector<node> g;

struct lols{
  int poz, c;
};

bool operator<(lols a, lols b){
  return a.c>b.c;
}

vector<int> dijkstra(int s, int d, int n){
  priority_queue<lols> q;
  q.push({s, 1});
  vector<int> sol(n+1);
  while(!q.empty()){
    auto x=q.top();
    while(!q.empty()&&sol[q.top().poz]) q.pop(), x=q.top();
    if(!q.empty()){
      lols x=q.top();
      q.pop();
      int nod=x.poz;
      int cost=x.c;
      sol[nod]=cost;
      for(auto i:g[nod].vec){
        if(i.d>=d){
          q.push({i.dest, cost+i.cost});
        }
      }
    }
  }
  for(int i=1;i<=n;++i) sol[i]--;
  return sol;
}

int main()
{
  int n, m;
  fin>>n>>m;
  g.resize(n+1);
  for(int i=1;i<=m;++i){
    int a, b, c;
    fin>>a>>b>>c;
    g[a].vec.push_back({b, c, 0});
  }
  vector<int> sol;
  sol=dijkstra(1, 0, n);
  for(int i=2;i<=n;++i){
    fout<<sol[i]<<" ";
  }
  return 0;
}