#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 n,int k)
{
    int son;
    do
    {
        son = 0;
        if(leftSon(k) <= n)
        {
            son = leftSon(k);
            if(rightSon(k) <= n && h[rightSon(k)] < h[leftSon(k)])
                son = rightSon(k);
            if(h[son] > h[k])
                son = 0;
        }

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

void upHeap(int n,int k)
{
    int key = h[k];

    while( k > 1 && key < h[father(k)] )
    {
        h[k] = h[father(k)];
        k = father(k);
    }

    h[k] = key;
}

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

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