#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#define N 50010
#define oo 1000000000

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector<pair<int, int> > v[N];
priority_queue<pair<int, int> > Q;
int d[N], n, m, a, b, c, viz[N], i;
pair<int, int> P;

int main()
{
    f >> n >> m;
    for(;m; m--)
    {
        f >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    for(i = 2; i <= n; i++)
        d[i] = oo;
    Q.push(make_pair(0, 1));
    while(Q.size())
    {
        P = Q.top(); Q.pop();
        c = -P.first;
        a = P.second;
        if(viz[a]) continue;
        viz[a] = 1;
        for(auto it:v[a])
        {
            if(d[it.first] > c + it.second)
            {
                d[it.first] = c + it.second;
                Q.push(make_pair(-d[it.first], it.first));
            }
        }
    }
    for(i = 2; i <= n; i++)
        if(d[i] == oo)
            g << "0 ";
        else g << d[i] << ' ';
    return 0;
}