#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int Nmax=50000;
const int oo=INT_MAX;

int N, M;
vector < pair<int, int> > G[Nmax+5];

int D[Nmax+5], size=1;
pair<int, int> H[Nmax+5];
bool use[Nmax+5];

int father(int nod)
{
    return nod/2;
}

int left_son(int nod)
{
    return nod*2;
}

int right_son(int nod)
{
    return nod*2+1;
}

int min()
{
    return H[1].first;
}

void sift(int k)
{
    int son=0;
    do
    {
        if (left_son(k)<=N)
        {
            son=left_son(k);
            if (right_son(k)<=N && right_son(k)<son)
                son=right_son(k);
        }

        if (H[son]>=H[k])
            son=0;
        else
        {
            swap(H[son], H[k]);
            k=son;
        }
    } while(son);
}

void percolate(int k)
{
    while (k>1 && H[k]<H[father(k)])
    {
        swap(H[k], H[father(k)]), k=father(k);

    }
}

void cut()
{
    H[1]=H[size];
    size--;
    if(size>0)
        sift(1);
}

void citire()
{
    fin >> N >> M;
    for (int i=1; i<=M; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }
}

void dijkstra(int start)
{
    for (int i=1; i<=N; i++)
        D[i]=oo;
    D[start]=0;
    H[1].first=start;
    H[1].second=0;

    for (int k=1; k<N; k++)
    {
        int nod=min();
        cut();

        for (int i=0; i<(int)G[nod].size(); i++)
        {
            int vecin=G[nod][i].first, cost=G[nod][i].second;
            D[vecin]=min(D[vecin], D[nod]+cost);

            size++;
            H[size].first=vecin;
            H[size].second=D[vecin];
            percolate(size);
        }
    }
}

void afisare()
{
    for (int i=2; i<=N; i++)
    {
        if (D[i]==oo)
            D[i]=0;
        cout << D[i] << " ";
    }
    cout << "\n";
}

int main()
{
    citire();
    dijkstra(1);
    afisare();
    return 0;
}