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

struct point {
    vector<int> a, b;
    bool used;
    bool in;
};
vector<long> d;
vector<point> g;

struct compare {
    bool operator()(const long &t1, const long &t2) const
    {
        return d[t1]>d[t2]?1:0;
    }
};

priority_queue<long, vector<long>, compare> index;

void dj(int i) {
    d[i] = 0;
    while(!index.empty()) {
        int current = index.top();
        index.pop();
        if(g[current].used) continue;
        g[current].used = true;
        for(int k=0;k<(int)g[current].a.size();k++) {
            if(!g[g[current].a[k]].used&&(d[g[current].a[k]]>d[current] + g[current].b[k]||d[g[current].a[k]]==-1)) {
                if(d[g[current].a[k]]== -1) d[g[current].a[k]] = 0;
                d[g[current].a[k]] = d[current] + g[current].b[k];
                index.push(g[current].a[k]);
                g[g[current].a[k]].in = true;
            }
        }
    }
}

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int n, m;
    in>>n>>m;
    point temp;
    temp.used = false;
    temp.in = false;
    g.resize(n+1, temp);
    d.resize(n+1, -1);
    d[1]=0;
    index.push(1);
    while(m-->0) {
        int x, y, z;
        in>>x>>y>>z;
        g[x].a.push_back(y);
        g[x].b.push_back(z);
    }
    in.close();
    dj(1);
    for(int k=2;k<(int)d.size();k++) {
        if(d[k]==-1) out<<0; else out<<d[k];
        out<<" ";
    }
    out.close();
    return 0;
}