#include <fstream>
#include <vector>
#include <queue>

#define NLen 0x10000
#define inf 0x7fffffff

using namespace std;

ifstream fi;
ofstream fo;

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

int dist[NLen];

int N;

class ComparePQ
{
    public:
        bool operator()(const int & a, const int & b)
        {
            return dist[a] > dist[b];
        }
};

inline void dij(int nod)
{
    priority_queue < int, vector < int > , ComparePQ > PQ;

    for(int i = 1; i <= N; ++ i) dist[i] = inf;

    dist[nod] = 0;
    PQ.push(nod);

    while( ! PQ.empty())
    {
        nod = PQ.top();
        PQ.pop();

        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;
                PQ.push(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 = 1; 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;
}