#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 {
    return weight < o.weight;
  }
};

int const INF = 1e6 + 1;
int const NMAX = 50000;
int n, m;

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

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;
      for(int i = 0; i < g[node].size(); i++) {
        int neighbor = g[node][i].neighbor;
        if(dist[neighbor] > dist[node] + g[node][i].weight) {
          pretenders.erase({neighbor, dist[neighbor]});
          dist[neighbor] = dist[node] + g[node][i].weight;
          pretenders.insert({neighbor, dist[neighbor]});
        }
      }
    }
  }
}

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++) {
    cout << dist[i] << " ";
  }
}