#include <fstream>
#include <vector>

#define NLen 0x10000
#define inf 0x7fffffff

using namespace std;

ifstream fi;
ofstream fo;

vector < pair < int, int > > G[NLen];

int DIST[NLen];
int h[NLen];
int pos[NLen];
int use[NLen];
int N;

inline void Up_Heap(int nod)
{
    int Old = h[nod];

    for(; nod > 1 && DIST[ h[nod >> 1] ] > DIST[Old]; nod >>= 1)
    {
        h[nod] = h[nod >> 1];
        pos[ h[nod] ] = nod;
    }

    h[nod] = Old;
    pos[Old] = nod;
}

inline void Down_Heap(int nod)
{
    int Old = h[nod], L, R;

    while(1)
    {
        L = nod << 1;
        R = L + 1;

        if(R <= h[0] && DIST[ h[L] ] > DIST[ h[R] ] && DIST[ h[R] ] < DIST[Old])
        {
            h[nod] = h[R];
            pos[ h[nod] ] = nod;
            nod = R;
        }
        else
        if(L <= h[0] && DIST[ h[L] ] < DIST[Old])
        {
            h[nod] = h[L];
            pos[ h[nod] ] = nod;
            nod = L;
        }
        else
        {
            h[nod] = Old;
            pos[ h[nod] ] = nod;
            return;
        }
    }
}

inline void Push_Heap(int nod)
{
    h[ ++ h[0] ] = nod;
    pos[nod] = h[0];
}

inline void Pop_Heap(int nod)
{
    if(h[0] == nod)
    {
        -- h[0];
        return;
    }

    h[nod] = h[ h[0] -- ];
    pos[ h[nod] ] = nod;

    if(nod > 1 && DIST[ h[nod >> 1] ] > DIST[ h[nod] ]) Up_Heap(nod);
    else Down_Heap(nod);
}

inline void dij(int nod)
{
    for(int i = 1; i <= N; ++ i)
    {
        DIST[i] = inf;
        h[i] = 0;
        pos[i] = 0;
        use[i] = 0;
    }

    DIST[nod] = 0;
    h[0] = 1;
    h[1] = nod;
    pos[nod] = 1;
    use[nod] = 1;

    while(h[0])
    {
        nod = h[1];
        Pop_Heap(1);

        for(int i = 0; i < G[nod].size(); ++ i)
            if(DIST[ G[nod][i].first ] == inf || DIST[ G[nod][i].first ] > DIST[nod] + G[nod][i].second)
            {
                DIST[ G[nod][i].first ] = DIST[nod] + G[nod][i].second;
                if( ! use[ G[nod][i].first ])
                {
                    use[ G[nod][i].first ] = 1;
                    Push_Heap(G[nod][i].first);
                }
                Up_Heap(pos[ G[nod][i].first ]);
            }
    }
}

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

    fi.open("dijkstra.in");

    fi >> N >> M;
    for(; M -- ; )
    {
        fi >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }

    fi.close();

    dij(1);

    fo.open("dijkstra.out");

    for(int i = 2; i <= N; ++ i)
        if(DIST[i] == inf) DIST[i] = 0;

    for(int i = 2; i <= N; ++ i) fo << DIST[i] << ' ';
    fo << '\n';

    fo.close();
    return 0;
}