#include <bits/stdc++.h>

using namespace std;

priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;

vector <int> s[50005];
vector <long long int> cc[50005];

long long int l[50005];

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int n,m,x,y,c;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y>>c;
        s[x].push_back(y);
        cc[x].push_back(c);
    }
    for(int i=1;i<=n;++i)
    {
        l[i]=LLONG_MAX;
    }
    l[1]=0;
    q.emplace(0,1);
    while(q.size())
    {
        int ct,in;
        ct=q.top().first;
        in=q.top().second;

        if (ct > l[in])
        {

        }
        else
        {


        for(int i=0;i<s[in].size();++i)
        {
            if(ct+cc[in][i]<l[s[in][i]])
            {
                l[s[in][i]]=ct+cc[in][i];
                q.emplace(l[s[in][i]],s[in][i]);
            }
        }
        }
        q.pop();
    }
    for(int i=2;i<=n;++i)
    {
        if(l[i]==LLONG_MAX)
        {
            l[i]=0;
        }
        cout<<l[i]<<" ";
    }
    return 0;
}