#include <iostream>
#include <set>
#include <vector>
#include <fstream>
#define node first
#define weight second
#define nmax 50005
#define inf (1<<30)
using namespace std;


void get_data (int &n, int &m, vector <pair <int, int > > v[nmax], set < pair<int, int> > s){
    // input: n -> integer (number of nodes)
    // m -> integer (number of edges)
    // x, y, w -> integers (edge from x to y of weight w
    int x, y, w;
    ifstream fin ("dijkstra.in");
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
        fin >> x >> y >> w;
        v[x].push_back (make_pair (y, w));
    }
}

void solve (int n, int m, vector < pair<int, int> > v[nmax], set <pair<int, int> > s, int dist[nmax]){
    dist[1] = 0;
    for (int i = 2; i <= n; i++)
        dist[i] = inf;
        s.insert (make_pair (0, 1));
        while (!s.empty()){
            int current_node = s.begin() -> second;
            int current_dist = s.begin() -> first;
            s.erase(*s.begin());
            for (auto x : v[current_node])
                if (dist[x.first] > current_dist + x.weight){
                    dist[x.first] = current_dist + x.weight;
                    s.insert (make_pair (dist[x.first], x.first));
                }
        }
}

void print_data (int n, int dist[]){
    ofstream fout ("dijkstra.out");
    for (int i = 2; i <= n; i++)
        if (dist[i] == inf)
            fout << 0 << " ";
        else
            fout << dist[i] << " ";
}

int main(){
    int n, m;
    int dist[nmax];
    set < pair <int, int> > s;
    vector < pair <int, int > > v[nmax];
    get_data (n, m, v, s);
    solve (n, m, v, s, dist);
    print_data (n, dist);
    return 0;
}