#include <fstream>
#include <vector>
#define INF 2000000000
#define DIM 50002

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, x, y, c, viz[DIM], t[DIM], h[DIM], dim, dimm, poz[DIM];

struct nodul
{
    long long nod;
    int cost;
}aux;

struct dist
{
    int val;
}d[DIM];

vector <nodul> graf[DIM];

void adauga(int nod)
{
    h[++dimm] = nod;
    dim = dimm;
    poz[h[dim]] = dim;
    while(d[h[dim]].val < d[h[dim / 2]].val && dim / 2 > 0)
    {
        swap(poz[h[dim]], poz[h[dim / 2]]);
        swap(h[dim], h[dim / 2]);
        dim /= 2;
    }
}

void scoate(int dim)
{
    swap(h[dim], h[dimm]);
    poz[h[dim]] = dim;
    --dimm;
    int ok = 1;
    while(ok)
    {
        ok = 0;
        if(2 * dim == dimm || (d[h[2 * dim]].val < d[h[2 * dim + 1]].val && 2 * dim + 1 <= dimm))
        {
            if(d[h[dim]].val > d[h[2 * dim]].val)
            {
                swap(poz[h[dim]], poz[h[2 * dim]]);
                swap(h[dim], h[2 * dim]);
                ok = 1;
                dim = 2 * dim;
            }
        }
        if(2 * dim + 1 <= dimm && ok == 0)
        {
            if(d[h[2 * dim + 1]].val <= d[h[2 * dim]].val)
            {
                if(d[h[2 * dim + 1]].val < d[h[dim]].val)
                {
                    swap(poz[h[dim]], poz[h[dim * 2 + 1]]);
                    swap(h[dim], h[2 * dim + 1]);
                    ok = 1;
                    dim = 2 * dim + 1;
                }
            }
        }
    }
}

void update(int dim)
{
    while(dim / 2 > 0 && d[h[dim]].val < d[h[dim / 2]].val)
    {
        swap(poz[h[dim]], poz[h[dim / 2]]);
        swap(h[dim], h[dim / 2]);
        dim /= 2;
    }
}

int main()
{
    f>>n>>m;

    for(int i = 1; i <= m; ++ i)
    {
        f>>x>>y>>c;
        aux.nod = y;
        aux.cost = c;
        graf[x].push_back(aux);
    }
    /*for(int i = 1; i <= n; ++ i)
    {
        for(int j = 0; j < graf[i].size(); ++ j)
            g<<graf[i][j].nod<<" ";
        g<<'\n';
    }
    g<<'\n';*/

    for(int i = 2; i <= n; ++ i)
    {
        d[i].val = INF;
        poz[i] = INF;
    }
    d[0].val = INF;

    adauga(1);
    viz[1] = 1;

    for(int i = 1; i <= n && dimm > 0; ++ i)
    {
        int nod = h[1];
        scoate(1);
        viz[nod] = 1;
        for(int j = 0; j < graf[nod].size(); ++ j)
        {
            aux = graf[nod][j];
            if(viz[aux.nod] == 0)
            {
                if(d[nod].val + aux.cost < d[aux.nod].val)
                {
                    d[aux.nod].val = d[nod].val + aux.cost;
                    if(poz[aux.nod] != INF)
                    {
                        update(poz[aux.nod]);
                    }
                    else
                        adauga(aux.nod);
                }

            }
        }
    }

    for(int i = 2; i <= n; ++ i)
    {
        if(d[i].val == INF)
            g<<"0 ";
        else
            g<<d[i].val<<" ";

    }

    return 0;
}