#include <bits/stdc++.h>

using namespace std;

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

struct Edge {
  int neighbor;
  int weight;

  bool operator < (Edge o) const {
    if(weight != o.weight) {
      return weight < o.weight;
    } else {
      return neighbor < o.neighbor;
    }
  }
};

int const INF = 1e9 + 1;
int const NMAX = 50001;
int n, m;

vector<Edge> g[1 + NMAX];
int dist[1 + NMAX];

void printset(set<Edge> s) {
  for(auto i : s) {
    cout << "{" << i.neighbor << ", " << i.weight << "} ";
  }
  cout << "\n\n";
}

void dijkstra(vector<Edge> g[1 + NMAX], int src, int dist[1 + NMAX]) {
  bool visited[1 + NMAX];
  for(int i = 1; i <= n; i++) {
    visited[i] = false;
    dist[i] = INF;
  }
  dist[src] = 0;
  set<Edge> pretenders;
  pretenders.insert({src, 0});
  while(!pretenders.empty()) {
    Edge e = *pretenders.begin();
    int node = e.neighbor;
    int distance = e.weight;
    pretenders.erase(e);
    if(!visited[node]) {
      visited[node] = true;
      //cout << node << " -> ";
      for(int i = 0; i < g[node].size(); i++) {
        int neighbor = g[node][i].neighbor;
        //cout << neighbor << " ";
        if(!visited[neighbor] && dist[neighbor] > dist[node] + g[node][i].weight) {
          if(pretenders.find({neighbor, dist[neighbor]}) != pretenders.end()) {
            pretenders.erase({neighbor, dist[neighbor]});
            //cout << "!D  ";
          } else {
            //cout << "!  ";
          }
          dist[neighbor] = dist[node] + g[node][i].weight;
          pretenders.insert({neighbor, dist[neighbor]});
          //cout << "INSERTED: " << neighbor << " " << dist[neighbor] << "\n";

          //printset(pretenders);
        }
      }
      //cout << "\n";
    }
    //printset(pretenders);
  }
}

int main() {
  fin >> n >> m;
  for(int i = 0; i < m; i++) {
    int a, b, c;
    fin >> a >> b >> c;
    g[a].push_back({b, c});
  }

  dijkstra(g, 1, dist);
  for(int i = 2; i <= n; i++) {
    if(dist[i] >= INF) {
      fout << 0 << " ";
    } else {
      fout << dist[i] << " ";
    }
  }
}