#include <iostream>
#include <fstream>
#include <queue>
#include <list>
#include <vector>

using namespace std;

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

const int NN = 50003, INF = 2e9;

int d[NN];

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

priority_queue <int, vector<int>,comp> Q;
//vector< pair<int, int> > graph[NN];
struct G{
    list<pair<int,int> > l;
}graph[NN];

int n,m;

void read(){
    in>>n>>m;
    while (m--){
        int x, y, c;
        in>>x>>y>>c;
        graph[x].l.push_back(make_pair (y, c));
    }
}

void dijk(int x){
    int y,c;
    for(int i=1;i<=n;i++)
        d[i]=INF;
    d[x]=0;
    Q.push(x);
    while (!Q.empty()){
        x=Q.top();
        Q.pop();
        int s=graph[x].l.size();
        for(int i=0;i<=s;i++){
            y=graph[x].l.front().first;
            c=graph[x].l.front().second;
            graph[x].l.pop_front();
            if (d[x]+c<d[y]) {
                d[y]=d[x]+c;
                Q.push(y);
            }

        }
    }
}

void afij (int x){
    for (int i=1;i<=n;i++){
        if(i==x) continue;
        if (d[i]==INF){
            out<<"0 ";
        }
        else{
            out<<d[i]<<' ';
        }
    }
}

int main () {
    read();
    dijk(1);
    afij(1);
    return 0;
}