#include <bits/stdc++.h>

using namespace std;

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

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

long long int l[50005];

int vs[50005];

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    long long 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())
    {
        long long int ct,in;
        ct=q.top().first;
        in=q.top().second;
        q.pop();

        if (ct > l[in] || vs[in]==1)
        {

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