#include <fstream>
#include <vector>
#include <set>
#include <cstring>
#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];
vector <per> v[nmax];

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 solve(){
    dist[1] = 0;
    for(int i = 2; i <= n; i++)
        dist[i] = inf;

    set <per> s;
    s.insert({1, 0});

    while(!s.empty()){
        int nod = s.begin()->first;
        s.erase(s.begin());

        vector <per>::iterator it;
        for(it = v[nod].begin(); it != v[nod].end(); it++){
            int to = it->first;
            int cost = it->second;

            if(dist[to] > dist[nod] + cost){
                if(dist[to] != inf)
                    s.erase(s.find({to, dist[to]}));
                dist[to] = dist[nod] + cost;
                s.insert({to, dist[to]});
            }
        }
    }
}

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

int main()
{
    read();
    solve();
    print();

    return 0;
}