#include <bits/stdc++.h>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int N = 50002;
const int oo = 1000000010;
vector<pair<int,int>> v[N];
priority_queue<pair<int,int>> pq;
int n,m,x,y,c,i,d[N];
int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(c,y));
    }
    for(i=2;i<=n;i++)
        d[i]=oo;
    pq.push(make_pair(0,1));
    while(pq.size())
    {
        tie(c,x)=pq.top();pq.pop();
        c=-c;
        if(c==d[x])
            for(auto it:v[x])
                ///it.first = costul muchiei de la x la vecinul curent
                ///it.second = vecinul curent
                if(d[it.second]>c+it.first)
                {
                    d[it.second]=c+it.first;
                    pq.push(make_pair(-d[it.second],it.second));
                }
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==oo)d[i]=0;
        g<<d[i]<<' ';
    }
    return 0;
}