#include <fstream>
#define maxim 50001
#include <list>
#include <queue>
#include <algorithm>
#include <cstdlib>

using namespace std;

struct muchie
{
    int l; short int vf;
};

struct drum
{
    int lung, varf;
    bool operator < (const drum& e) const
        {
            return lung>e.lung;
        }
};

priority_queue <drum> cd;

drum d;

muchie x;

list <muchie> nod[maxim];

int dist[maxim], viz[maxim], n, m, a, b, lungime, vfm;

int stab_drum(int varf)
    {
        int v=vfm;
        for (list<muchie>::iterator j=nod[varf].begin(); j!=nod[varf].end(); ++j)
            {
                x=*j;
                if(dist[x.vf]>(dist[varf]+x.l)||dist[x.vf]==0)
                    {
                        dist[x.vf]=dist[varf]+x.l;
                        d.lung=dist[x.vf];
                        d.varf=x.vf;
                        cd.push(d);
                    }
            }
        d=cd.top();
        cd.pop();
        v=d.varf;
        return v;
    }

int main()
{
    ifstream in ("dijkstra.in");
    ofstream out ("dijkstra.out");
    in>>n>>m;
    while(m--)
        {
            in>>a>>b>>lungime;
            x.vf=b;
            x.l=lungime;
            nod[a].push_back(x);
        }
    vfm=1;
    for(int i=1; i<=n; ++i)
        {
            viz[vfm]=1;
            vfm=stab_drum(vfm);
        }
    for(int i=2; i<=n; ++i)
        out<<dist[i]<<" ";
    in.close();
    out.close();
    return 0;
}