#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

#define dim 100010
#define inf 0x3f3f3f3f

int n, m, p;
int d[dim], v[dim];
vector<pair<int,int>> V[dim];

struct comp{
    bool operator()(int a, int b){
        return d[a] > d[b];
    }
};

priority_queue<int,vector<int>,comp>Q;

void dij(int p){
    for(int i = 2; i <= n; i++)
        d[i] = inf;
    v[1] = 1;
    Q.push(1);

    while(!Q.empty()){
        int nod = Q.top();
        v[nod] = 0;
        Q.pop();

        for(auto vec : V[nod]){
            int nbr=vec.first;
            int cst=vec.second;

            if(d[nbr] > cst + d[nod]){
                d[nbr] = cst + d[nod];
                if(!v[nbr])
                    Q.push(nbr), v[nbr] = 1;
            }
        }
    }

    for(int i = 2; i <= n; i++)
        if(d[i] != inf) cout << d[i] << " ";
        else
            cout << 0 << " ";
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        V[x].push_back({y,c});
    }
    dij(p);
    return 0;
}