#include <algorithm>
#include <fstream>
#include <iostream>
#include <set>
#include <vector>
#include <queue>
using namespace std;

#define destination first
#define cost second

const int MAX_N = 50100;
const int INF = 1 << 30;

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

int N, M;
vector<pair<int, int>> graph[MAX_N];
int dist[MAX_N];
bool visited[MAX_N];

void read_input();
void dijkstra(int source);
void print_output();

int main() {
    read_input();
    dijkstra(1);
    print_output();
    return 0;
}

void read_input() {
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
    }
}

struct HeapCmp {
    bool operator() (int lhs, int rhs) {
        return dist[lhs] > dist[rhs];
    }
};

void dijkstra(int source) {
    fill(dist, dist + N + 1, INF);

    priority_queue<pair<int, int>> heap;
    heap.push(make_pair(0, source));
    
    while (!heap.empty()) {
        int node = heap.top().second;
        int d = -heap.top().first;
        heap.pop();

        if (dist[node] != INF) continue;
        dist[node] = d;

        for (auto edge : graph[node]) {
          if (d + edge.cost < dist[edge.destination]) {
              heap.push(make_pair(-(d + edge.cost), edge.destination));
          }
        }
    }
}

void print_output() {
    for (int i = 2; i <= N; ++i) {
        fout << (dist[i] == INF ? 0 : dist[i]) << ' ';
    }
}