#include <fstream>
#define INF 1 << 30

using namespace std;

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

struct Nod
{
    int nod,cost;
    Nod *urm;
};

typedef Nod *PNod;

PNod L[50001];
int d[50001],viz[50001],n,m;

void add(int x, int y, int c)
{
    PNod p = new Nod;
    p -> nod = y;
    p -> cost = c;
    p -> urm = L[x];
    L[x] = p;
}

void dijkstra()
{
    for(int i = 2; i <= n; i++)
        d[i] = INF;

    for(int i = 1; i <= n; i++)
    {
        int minn,pminn;

        minn = INF;
        for(int j = 1; j <= n; j++)
            if(d[j] < minn && !viz[j])
            {
                minn = d[j];
                pminn = j;
            }

        viz[pminn] = 1;

        PNod p = L[pminn];

        while(p)
        {
            if( d[p -> nod] > d[pminn] + p -> cost)
                d[p -> nod] = d[pminn] + p -> cost;

            p = p -> urm;
        }

    }
}

int main()
{
    int x,y,c;

    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        add(x,y,c);
    }

    dijkstra();

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