#include <fstream>
#define maxim 50001
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

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

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

bool comp (const int &e, const int &f)
{
    return dist[e]>dist[f];
}

muchie x;

vector <muchie> nod[maxim];

vector <int> h;

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);
        }
    h.push_back(1);
    make_heap(h.begin(), h.end(), comp);
    for(int i=1; i<=n; ++i)
        {
            pop_heap(h.begin(), h.end(), comp);
            vfm=h.back();
            h.pop_back();
            viz[vfm]=1;
            vfc=vfm;
            for (vector<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;
                        if(inside[x.vf]==0)
                        {
                            h.push_back(x.vf);
                            push_heap(h.begin(), h.end(), comp);
                            inside[x.vf]=1;
                        }
                    }
            }
        }
    for(int i=2; i<=n; ++i)
        out<<dist[i]<<" ";
    out<<"\n";
    in.close();
    out.close();
    return 0;
}