#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 5e4 + 5, M_MAX = 25e4 + 5, INF = 1 << 28;
int N, M;
int dist[N_MAX];
bitset<N_MAX> viz;

struct Edge
{
    int v, c;

    Edge(int _v, int _c) :
        v(_v), c(_c) {}

    Edge() {}
};

struct Cmp
{
    inline bool operator()(const Edge& a, const Edge& b)
    {
        return a.c > b.c;
    }
};

vector<Edge> G[N_MAX];

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadInput()
{
    cin >> N >> M;

    for(int i = 0, v1, v2, c; i < M; i++)
    {
        cin >> v1 >> v2 >> c;
        G[v1].emplace_back(v2, c);
    }
}

void Dijkstra(int start)
{
    priority_queue<Edge, vector<Edge>, Cmp> PQ;

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

    PQ.emplace(start, 0);

    Edge E;
    while(not PQ.empty())
    {
        E = PQ.top();
        PQ.pop();

        if(viz[E.v])
            continue;

        dist[E.v] = E.c;
        viz[E.v] = 1;

        for(auto fiu : G[E.v])
            if(not viz[fiu.v])
                PQ.emplace(fiu.v, E.c + fiu.c);
    }

    for(int i = 2; i <= N; i++)
        cout << dist[i] << ' ';
}

int main()
{
    SetInput("dijkstra");

    ReadInput();
    Dijkstra(1);

    return 0;
}