#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
using namespace std;
typedef pair<int, int> pi;
int n, m;
struct elem
{
    bool vizitat;
    int cost=(1<<30);
    priority_queue <pi,vector<pi>, greater<pi> >M;
    vector <pi> v;
};
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    elem noduri[n+1];
    {
        for (unsigned int i=1; i<=n; i++)
            noduri[i].vizitat=false;
    }
    {
    unsigned int nod, legatura, cost;
    for(unsigned int i=1; i<=m; i++)
        {
            f>>nod>>legatura>>cost;
            noduri[nod].M.push(make_pair(cost,legatura));
            noduri[nod].v.push_back(make_pair(cost, legatura));
        }
    }
    f.close();
    noduri[1].cost=0;



    //
    {
        int curent=1, next, pozitieUrmatoare, CostUrmator, ok;
        for (int p=1; p<=n; p++)
        {
            curent =p;
            next=0;
            if (noduri[p].vizitat==false)
            {
            noduri[p].vizitat=true;
            while (next!=-1)
            {
            ok=1;
            if (!noduri[curent].M.empty())
            next=noduri[curent].M.top().second; else
            next=-1;
            while (!noduri[curent].M.empty())
                {
                    if (noduri[next].vizitat==true)
                            {ok=0;
                             next=-1;
                            }
                    if (ok==0)
                    {
                            next=noduri[curent].M.top().second;
                            ok=1;
                    }
                    if (noduri[next].vizitat==true)
                    {ok=0;
                    next=-1;
                    }
                    pozitieUrmatoare=noduri[curent].M.top().second;
                    CostUrmator=noduri[curent].M.top().first+noduri[curent].cost;
                    if (noduri[pozitieUrmatoare].cost>CostUrmator)
                    {
                        noduri[pozitieUrmatoare].cost=CostUrmator;
                        noduri[pozitieUrmatoare].vizitat=false;
                        {
                            for (unsigned int i=0; i<noduri[pozitieUrmatoare].v.size(); i++)
                            {
                                int c, p;
                                c=noduri[pozitieUrmatoare].v[i].first;
                                p=noduri[pozitieUrmatoare].v[i].second;
                                noduri[pozitieUrmatoare].M.push(make_pair(c,p));
                            }
                        }
                    }
                    noduri[curent].M.pop();
                }
            noduri[curent].vizitat=true;
            if (next!=-1)
                curent=next;
        }
        }
        }
        for (unsigned int i=2; i<=n; i++)
            if (noduri[i].cost!= (1<<30))
                g<<noduri[i].cost<<" "; else
                g<<"0"<<" ";
}
    return 0;
}