#include <bits/stdc++.h>
#define pii pair <int, int>

using namespace std;

const int nmax=5e4+3, inf=1e9;
int d[nmax];
vector <pii> v[nmax];
priority_queue <pii, vector <pii>, greater<pii> > pq;

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    int n, m, a, b, c;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>a>>b>>c;
        v[a].push_back({b, c});
    }

    for(int i=1; i<=n; i++) d[i]=inf;
    pq.push({0, 1});
    d[1]=0;
    int co, nod;
    while(!pq.empty())
    {
        co=pq.top().first;
        nod=pq.top().second;
        pq.pop();
        if(co>d[nod]) continue;

        for(pii p:v[nod])
        {
            b=p.first;
            c=p.second;
            if(d[nod]+c<d[b])
            {
                d[b]=d[nod]+c;
                pq.push({d[b], b});
            }
        }
    }
    for(int i=2; i<=n; i++)
    {
        if(d[i]==inf) cout<<0<<' ';
        else cout<<d[i]<<' ';
    }

    return 0;
}