#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define MAXX 200000

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector <pair<int, int> > G[50010];
priority_queue <pair<int, int> > PQ;

int n,m,d[50010],viz[50010];

void Dijkstra(int x)
{
    for(int i=1;i<=n;i++)
        d[i]=MAXX;
    d[x]=0;
    viz[x]=1;
    {
        int nod=x;
        int nr=G[nod].size();
        for(int i=0;i<nr;i++)
            {
            d[G[nod][i].first]=G[nod][i].second;
            PQ.push(make_pair(-d[G[nod][i].first],G[nod][i].first));
            }
    }
    while(PQ.size())
    {
        pair <int,int> val=PQ.top();
        PQ.pop();
        int nod=val.second;

        if(viz[nod]==0)
        {
            viz[nod]=1;
            int nr=G[nod].size();
            for(int i=0;i<nr;i++)
                if(viz[G[nod][i].first]==0 && d[G[nod][i].first]>d[nod]+G[nod][i].second)
            {
                d[G[nod][i].first]=d[nod]+G[nod][i].second;
                PQ.push(make_pair(-d[G[nod][i].first],G[nod][i].first));
            }
        }
    }
    for(int i=1;i<=n;i++)
        cout<<d[i]<<' ';
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
    }
    /*for(int i=1;i<=n;i++)
    {
        cout<<i<<": ";
        for(int j=0;j<G[i].size();j++)
            cout<<G[i][j].first<<' '<<G[i][j].second<<' ';
        cout<<'\n';
    }*/
    Dijkstra(3);


    return 0;
}