#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 50005;
const int inf = 1e9;

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

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

    for(int i = 1; i <= m; i++){
        int a, b, c;
        fin >> a >> b >> c;
        v[a].push_back({b, c});
    }
}

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

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

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

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

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

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

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

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

    return 0;
}