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

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

struct muchie{
    int st;
    long long lung;
};

int n,m;
vector<muchie>ad[50005];
long long len[50005];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

int main() {
    int a,b,c,vf;
    long long l;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        ad[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++)
        len[i]=1e18;
    len[1]=0;
    pq.push({0,1});
    while(!pq.empty()){
        l=pq.top().first;
        vf=pq.top().second;
        pq.pop();
        if(l>len[vf])
            continue;
        for(muchie&i:ad[vf])
            if(len[i.st]>len[vf]+i.lung) {
                len[i.st]=len[vf]+i.lung;
                pq.push({len[i.st],i.st});
            }
    }
    for(int i=2;i<=n;i++) {
        if (len[i]==1e18) {
            len[i]=0;
        }
        cout<<len[i]<<" ";
    }
    return 0;
}