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

struct point {
    vector<int> a, b;
};
vector<int> d;
vector<int> index;
vector<point> g;
int t=1;

bool cmp(const int &a, const int &b) { return d[a]>d[b]?1:0; }

void dj(int i) {
    while(!index.empty()) {
        int current = index.front();
        pop_heap(index.begin(), index.end(), cmp);
        index.pop_back();
        for(int k=0;k<(int)g[current].a.size();k++) {
            if(d[g[current].a[k]]>d[current] + g[current].b[k]) {
                d[g[current].a[k]] = d[current] + g[current].b[k];
                sort_heap(index.begin(), index.end(), cmp);
            }
        }
    }
}

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int n, m;
    in>>n>>m;
    g.resize(n+1);
    d.resize(n+1, 1001);
    d[1]=0;
    for(int k=1;k<(int)d.size();k++) index.push_back(k);
    make_heap(index.begin(), index.end(), cmp);
    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]==1001) out<<0; else out<<d[k];
        out<<" ";
    }
    out.close();
    return 0;
}