#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;

struct nodul
{
    int nod, cost;
}aux;

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

vector <nodul> graf[DIM];

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

void scoate(int dim)
{
    swap(h[dim], h[dimm]);
    d[h[dim]].h = 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(h[dim], h[2 * dim]);
                d[h[dim]].h = dim;
                d[h[2 * 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(h[dim], h[2 * dim + 1]);
                    d[h[dim]].h = dim;
                    d[h[2 * dim + 1]].h = 2 * dim + 1;
                    ok = 1;
                    dim = 2 * dim + 1;
                }
            }
        }
    }
}

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;
        d[i].h = 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(d[aux.nod].h != INF)
                    {
                        scoate(d[aux.nod].h);
                    }
                    adauga(aux.nod);
                }

            }
        }
    }

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

    }

    return 0;
}