#include<bits/stdc++.h>

#define nmax 50011

using namespace std;

vector <pair<int,int>>d[nmax];


struct cmp
{
    bool operator()(const pair<int,int>&a,const pair<int,int>&b) const
     {

        return a.second > b.second ;
     }

};


int dist[nmax],i,m,n,cost,a,b;
priority_queue <pair<int,int>,vector<pair<int,int>>,cmp>coada ;

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    while(m--)
    {

        f>>a>>b>>cost;
        d[a].push_back(make_pair(b,cost));

    }
    dist[1]=0;
    for(i=2;i<=n;i++)
    {

        dist[i]=1<<30;

    }
    coada.push(make_pair(1,dist[1]));
    while(!coada.empty())
    {
        int nod=coada.top().first;
        cost=coada.top().second;
        coada.pop();
        for(auto x:d[nod])
        {

            if(dist[x.first]>dist[nod]+x.second)
            {
                dist[x.first]=dist[nod]+x.second;
                coada.push(make_pair(x.first,dist[x.first]));

            }
         }
    }
    for(i=2;i<=n;i++)
    {
        if (dist[i]==1<<30)
            g<<0<<' ' ;
        else
            g<<dist[i]<<' ' ;
    }

    return 0;
}