#include <fstream>
#include <queue>
#include <vector>
#define per pair<int,int>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

const int nmax = 5e4 + 5;
const int inf = 1e9;

int n, m, dist[nmax];
bool vis[nmax];
vector <per> v[nmax];
priority_queue <per> pq;

void read(){
    cin >> n >> m;

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

void dijkstra(int x){
    for(int i = 1; i <= n; i++)
        dist[i] = inf;
    dist[x] = 0;

    pq.push({-dist[x], x});

    while(!pq.empty()){
        int nod = pq.top().second;
        pq.pop();

        if(vis[nod])
            continue;
        vis[nod] = 1;

        for(auto it: v[nod]){
            int y = it.first;
            int z = it.second;

            if(dist[nod] + z < dist[y]){
                dist[y] = dist[nod] + z;
                pq.push({-dist[y], y});
            }
        }
    }
}

void print(){
    for(int i = 2; i <= n; i++){
        if(dist[i] == inf)
            dist[i] = 0;
        cout << dist[i] << " ";
    }
}

int main()
{
    read();
    dijkstra(1);
    print();

    return 0;
}