#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct my_comparator
{
    // queue elements are vectors so we need to compare those
    bool operator()(pair<int, int> const& a, pair<int, int> const& b) const
    {
        // reverse sort puts the lowest value at the top
        return a.second >= b.second;
    }
};

// node + distance
priority_queue<pair<int, int>, vector<pair<int, int>>, my_comparator> pq;

vector<vector<pair<int, int>>> G;
vector<int> distances;
vector<bool> visited;
int n, m;

void read() {
    f>>n>>m;
    G.resize(n + 1);
    visited.resize(n + 1, 0);
    distances.resize(n + 1, INT_MAX);

    distances[1] = 0;
    pq.push(make_pair(1, 0));


    int x, y, w;
    while(f>>x>>y>>w) {
       G[x].push_back(make_pair(y, w));
    }
}

void Dijkstra(){
    while(pq.size()) {
        pair<int, int> top = pq.top();
        pq.pop();
        visited[top.first] = 1;

        for(auto a : G[top.first])
            if(top.second + a.second < distances[a.first] && !visited[a.first]) {
                    distances[a.first] = top.second + a.second;
                    pq.push(make_pair(a.first, distances[a.first]));
            }

    }

    for(int i = 2; i < n + 1; i++) {
        if(distances[i] == INT_MAX)
                distances[i] = 0;
        g<<distances[i]<<' ';
    }
}
int main()
{
    read();
    Dijkstra();
    f.close();
    g.close();
    return 0;
}