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

using namespace std;

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

const int Nmax=50000;
const int oo=1e9;

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)<=size)
        {
            son=left_son(k);
            if (right_son(k)<=size && H[right_son(k)].second<H[son].second)
                son=right_son(k);
        }

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

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

void build_heap(int k)
{
    for (int i=k/2; i>=1; i--)
        {
            sift(i);
        }
}

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;

    while(size>0)
    {

//        for (int i=1; i<=size; i++)
//            cout << "n:" <<H[i].first << " d:" << H[i].second << endl;
//        cout << endl << endl;
        int nod=min();
        cut();
        while (size>0 && use[H[1].first])
        {
            cut();
        }
//        cout << "Heap after cut: \n";
//        for (int i=1; i<=size; i++)
//            cout << "n:" <<H[i].first << " d:" << H[i].second << endl;
//        cout << endl << endl;

        use[nod]=1;

        for (int i=0; i<(int)G[nod].size(); i++)
        {
            int vecin=G[nod][i].first, cost=G[nod][i].second;
            if (D[nod]+cost<D[vecin])
            {
                D[vecin]=D[nod]+cost;
                //if (use[vecin]==0)
                {
                    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;
        fout << D[i] << " ";
    }
    fout << "\n";
}

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