///CEL MAI OPTIM
/// O(nlogn)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct elem
{
    int dest, cost;

    bool operator < (const elem &other) const///schimbarea semnului in prioirty queue
    {
        return cost > other.cost;
    }
};

vector <elem> v[50005];

priority_queue <elem> pq;///sorteaza in log(n)

int dist[50005];
int 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)///Intotdeauna prima valoare este cea corecta
            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++)
        if(dist[i] != INT_MAX) fout << dist[i] << " ";
        else fout << 0;
}

int main()
{

    fin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        fin >> x >> y >> z;
        v[x].push_back({y,z});
    }

    for(int i = 1; i <= n; i++)
        dist[i] = INT_MAX; ///Inititalizarea vectorului de distanta

    dijkstra(1);
}