#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

typedef long long ll;

ll n, m;

struct edgeD{
  ll dest;
  ll cost;
};

int const nmax = 5e4;
vector <edgeD> adj[1 + nmax];

ll dist[1 + nmax];
//ll prev[1 + nmax];

bool isVisited[1 + nmax];

void computeDij(){

  set<pair<int,int>> pq;

  for(int i = 1;i <= n;i++){
    dist[i] = 1e12;
   //prev[i] = 0;
    isVisited[i] = false;
  }
  pq.insert({0, 1});
  dist[1] = 0;
  while(pq.empty() == false){
    int nod = pq.begin()->second;
    //dist[nod] = pq.begin()->first;
    pq.erase(pq.begin());
    for(int i = 0;i < adj[nod].size();i++){
      if(isVisited[adj[nod][i].dest] == false){
        if(dist[adj[nod][i].dest] > dist[nod] + adj[nod][i].cost){
          dist[adj[nod][i].dest] = dist[nod] + adj[nod][i].cost;
          //pq.erase(dist[adj[nod][i].dest], adj[nod][i].dest);
          //prev[]
          pq.insert({dist[adj[nod][i].dest], adj[nod][i].dest});
        }
      }
    }
  }
}

int main() {

  ll a, b, cost;
  in >> n >> m;
  for(ll i = 1;i <= m;i++){
    in >> a >> b >> cost;
    adj[a].push_back({b, cost});
  }
  computeDij();
  for(ll i = 2;i <= n;i++){
    out << (dist[i] % (1LL * 1000000000000)) << ' ';
  }
  return 0;
}