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

using namespace std;

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

inline int leftSon(int k){return 2 * k;}
inline int rightSon(int k){return 2 * k + 1;}
inline int father(int k){return k / 2;}

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

typedef Nod *PNod;

int h[50001],d[50001],poz[50001],k,n,m;
PNod L[50001];

void downHeap(int x)
{
    int son;
    do
    {
        son = 0;
        if( leftSon(x) <= k )
        {
            son = leftSon(x);
            if( rightSon(x) <= k && d[ h[rightSon(x)] ] < d[ h[leftSon(x)] ] )
                son = rightSon(x);

            if( d[ h[son] ] > d[ h[x] ])
                son = 0;
        }

        if(son)
        {
            poz[ h[x] ] = son;
            poz[ h[son] ] = x;
            swap(h[x],h[son]);
            x = son;
        }
    }while(son);
}

void upHeap(int x)
{
    while(x > 1 && d[ h[x] ] < d[ h[father(x)] ])
    {
        poz[ h[x] ] = father(x);
        poz[ h[father(x)] ] = x;
        swap(h[x],h[father(x)]);
        x = father(x);
    }
}

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_heap()
{
    for(int i = 2; i <= n; i++)
        d[i] = INF, poz[i] = -1;
    poz[1] = 1;
    h[++k] = 1;

    while( k )
    {
        int minn = h[1];
        swap(h[1],h[k]);
        poz[ h[1] ]  = 1;
        k--;

        downHeap(1);

        PNod q = L[minn];

        while( q )
        {
            if(d[q -> nod] > d[minn] + q -> cost)
            {
                d[q -> nod] = d[minn] + q -> cost;

                if(poz[q -> nod] != -1)
                    upHeap( poz[q -> nod] );
                else
                {
                    h[++k] = q -> nod;
                    poz[ h[k] ] = k;
                    upHeap( k );
                }
            }
            q = q -> 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_heap();

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