#include <fstream>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int noduri, muchii, i, a, b, ok, lungime, cate[50005], t[50005], tata[50005], d[50005], minim, poz;

struct Nod
{
    int valoare;
    int cu_cn;
    struct Nod* urm;
};

typedef struct Nod* Lista;

Lista v[5000];

void inserare(Lista &p, int b, int lung)
{
    Lista q = new Nod;
    q->urm = p;
    q->valoare = lung;
    q->cu_cn = b;
    p = q;
}

void scoate(Lista &p)
{
    Lista copie;
    int x;
    for(copie=p; copie!=NULL; copie=copie->urm)
    {
        x = copie->cu_cn;
        if(d[x] == 0)
        d[x] = minim+copie->valoare;
        else
        d[x] = min(d[x], minim+copie->valoare);
        tata[x] = poz;
    }
}
void afisare(Lista p)
{
    fout << "AFISARE\n";
    for(Lista copie=p; copie!=NULL; copie=copie->urm)
    {
        fout << copie->cu_cn << ' ' << copie->valoare;
        fout << '\n';
    }
    fout << '\n';
}

int main()
{
    fin >> noduri >> muchii;
    for(i=1; i <= muchii; i++)
    {
        fin >> a >> b >> lungime;
        inserare(v[a], b, lungime);
        //afisare(v[a]);
    }
    d[1] = 1;
    while(ok == 0)
    {
        minim = 99999999;
        for(i=1; i <= noduri; i++)
        {
            if(t[i] == 0 && minim > d[i] && d[i] != 0)
            {
                minim = d[i];
                poz = i;
            }
        }
        if(minim == 99999999)
        break;
        t[poz] = 1;
        scoate(v[poz]);
    }
    for(i=2; i <= noduri; i++)
    fout << d[i]-1 << ' ';
}