#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;
};
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    unsigned int i,j;
    f>>n>>m;
    elem noduri[n+1];
    {
        for (int i=1; i<=n; i++)
            noduri[i].vizitat=false;
    }
    queue <int> viz;
    {
    unsigned int nod, legatura, cost;
    for(i=1; i<=m; i++)
        {
            f>>nod>>legatura>>cost;
            noduri[nod].M.push(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;
            viz.push(curent);
            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[curent].M.pop();
                }
            noduri[curent].vizitat=true;
            if (next!=-1)
                curent=next;
        }
        }
        }
        for (i=2; i<=n; i++)
            g<<noduri[i].cost<<" ";
        g<<"\n";
        }
    return 0;
}