#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

struct edge
{
    int nod, cost;
};
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n,m;
    f>>n>>m;
    vector< vector<edge> >G(n+1);
    int inf=(n-1)*20000;
    vector<int>d(n+1,inf);
    int a, b, cost;
    edge nod;
    for(int i=0;i<m;i++)
    {
        f>>a>>b>>cost;
        nod.nod=b;
        nod.cost=cost;
        G[a].push_back(nod);
    }

    d[1]=0;
    set< pair<int,int> >s;
    s.insert(make_pair(0,1));
    for(int i=1;i<=n;i++)
    {
        int ind=(*s.begin()).second;
        s.erase(s.begin());

        /*for(int j=0;j<G[ind].size();j++)
        {
            if(d[G[ind][j].nod]>d[ind]+G[ind][j].cost)
            {
                s.erase(make_pair(d[G[ind][j].nod],G[ind][j].nod));
                d[G[ind][j].nod]=d[ind]+G[ind][j].cost;
                s.insert(make_pair(d[G[ind][j].nod],G[ind][j].nod));
            }
        }*/
        /*vector<edge>::iterator j;
        for(j=G[ind].begin();j<G[ind].end();j++)
        {
            if(d[(*j).nod]>d[ind]+(*j).cost)
            {
                s.erase(make_pair(d[(*j).nod],(*j).nod));
                d[(*j).nod]=d[ind]+(*j).cost;
                s.insert(make_pair(d[(*j).nod],(*j).nod));
            }
        }*/
        for(auto edge:G[ind])
        {
            if(d[edge.nod]>d[ind]+edge.cost)
            {
                s.erase(make_pair(d[edge.nod],edge.nod));
                d[edge.nod]=d[ind]+edge.cost;
                s.insert(make_pair(d[edge.nod],edge.nod));
            }
        }

    }
    for(int i=2;i<=n;i++)
        if(d[i]==inf)
            g<<"0"<<" ";
        else g<<d[i]<<" ";

    f.close();
    g.close();
    return 0;
}