#include <bits/stdc++.h>

using namespace std;

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

struct elem
{
    int dest, cost;

    bool operator < (const elem &other) const
    {
        return cost > other.cost;
    }
};

vector <elem> v[50005];

priority_queue <elem> pq;

int dist[50005], n, m;

void dijkstra(int node)
{
    pq.push({1, 0});

    while(!pq.empty())
    {
        int node = pq.top().dest;
        int cost = pq.top().cost;

        pq.pop();

        if(dist[node] == INT_MAX)
            dist[node] = cost;

        cost = dist[node];

        for(int i = 0; i < v[node].size(); ++ i)
            if(dist[v[node][i].dest] > v[node][i].cost + cost)
        pq.push({v[node][i].dest, v[node][i].cost + cost});
    }

    for(int i = 2; i <= n; ++ i)
        g << dist[i] << " ";
}

int main()
{
    f >> n >> m;

    for(int i = 1; i <= m; ++ i)
    {
        int x, y, z;

        f >> x >> y >> z;

        v[x].push_back({y, z});
    }

    for(int i = 1; i <= n; ++ i)
        dist[i] = INT_MAX;

    dijkstra(1);

    return 0;
}