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

using namespace std;

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

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

struct drum
{
    int varf;
    bool operator < (const drum& e) const
        {
            return dist[varf]>dist[e.varf];
        }
};

priority_queue <drum> cd;

drum d;

muchie x;

list <muchie> nod[maxim];

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;
            vfc=vfm;
            for (list<muchie>::iterator j=nod[vfc].begin(); j!=nod[vfc].end(); ++j)
            {
                x=*j;
                if(dist[x.vf]>(dist[vfc]+x.l)||dist[x.vf]==0)
                    {
                        dist[x.vf]=dist[vfc]+x.l;
                        d.varf=x.vf;
                        cd.push(d);
                    }
            }
            v=1;
            while(viz[v]==1&&!cd.empty())
            {
                d=cd.top();
                cd.pop();
                v=d.varf;
            }
            vfm=v;
        }
    for(int i=2; i<=n; ++i)
        out<<dist[i]<<" ";
    in.close();
    out.close();
    return 0;
}