#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

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

const int mx=60000;
const long long inf=2e18;

struct edge{
    int dest;
    long long cost;
};
struct node{
    int index;
    long long cost;
};

struct comparator{
    bool operator()(node&a,node&b){
        return a.cost>b.cost;
    }
};

int n,m;
long long result[mx];
vector<edge> g[mx];

void read(){
    in>>n>>m;
    int a,b;
    long long c;
    for(int i=0;i<m;i++){
        in>>a>>b>>c;
        g[a].push_back({b,c});
    }
}

void solve(){
    for(int i=1;i<=n;i++){
        result[i]=inf;
    }

    priority_queue<node,vector<node>,comparator> q;
    q.push({1,0});
    result[1]=0;

    while(!q.empty()){
        node top=q.top();
        q.pop();

        if(top.cost>result[top.index])
            continue;

        for(edge next:g[top.index]){
            int fw=next.dest;

            if(result[fw]>top.cost+next.cost){
                result[fw]=top.cost+next.cost;
                q.push({fw,result[fw]});
            }
        }
    }

    for(int i=2;i<=n;i++){
        if(result[i]==inf)
            result[i]=0;
        out<<result[i]<<" ";
    }
}

int main(){
    read();
    solve();
    return 0;
}