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

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

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

void dj(int i) {
    d[i] = 0;
    priority_queue<int, vector<int>, compare> index;
    index.push(i);
    while(!index.empty()) {
        int current = index.top();
        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];
                index.push(g[current].a[k]);
            }
        }
        index.pop();
    }
}

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);
    while(m-->0) {
        int x, y, z;
        in>>x>>y>>z;
        g[x].a.push_back(y);
        //g[y].a.push_back(x);
        g[x].b.push_back(z);
        //g[y].b.push_back(z);
    }
    in.close();
    dj(1);
    for(int k=2;k<(int)d.size();k++) {
        out<<(d[k]==1001?0:d[k])<<" ";
    }
    out.close();
    return 0;
}