#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;
int use[Nmax+5];
pair<int, int> H[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 cut()
{
    H[1]=H[size];
    size--;
    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 initializare(int start)
{
    size=N;
    for (int i=1; i<=N; i++)
        D[i]=oo, H[i]=make_pair(i, oo);
    D[start]=0;
    H[1].first=start;
    H[1].second=0;
}

void dijkstra(int start=1)
{
    initializare(start);

    while(size>0)
    {
        int nod=min();
        cut();
        use[nod]=1;
        while (size>1 && use[H[1].first])
            cut();

        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;
                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();
    afisare();
    return 0;
}