#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));
    //vector<edge>::iterator i;
    for(int i=1;i<=n;i++)
    {
        int ind=(*s.begin()).second;
        s.erase(s.begin());
        //for(i=G[ind].begin();i<G[ind].end();i++)
        for(int i=0;i<G[ind].size();i++)
        {
            if(d[G[ind][i].nod]>d[ind]+G[ind][i].cost)
            {
                s.erase(make_pair(d[G[ind][i].nod],G[ind][i].nod));
                d[G[ind][i].nod]=d[ind]+G[ind][i].cost;
                s.insert(make_pair(d[G[ind][i].nod],G[ind][i].nod));
            }
        }
        //vector<edge>::iterator j;
        //for()

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

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