#include <bits/stdc++.h>

using namespace std;

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

struct str {
    int nod,cost;
};

int n,m,st;
vector<int>d,s;
vector<vector<pair<int,int>>>a;

void DEsopo(int st) {
    d[st]=0;
    deque<int>q;
    q.push_back(st);
    while (!q.empty()) {
        int nod=q.front();
        q.pop_front();
        s[nod]=0;
        for (auto f:a[nod]) {
            if (d[f.first]>d[nod]+f.second) {
                d[f.first]=d[nod]+f.second;
                if (s[f.first]==2) {
                    s[f.first]=1;
                    q.push_back(f.first);
                }else if (s[f.first]==0) {
                    s[f.first]=1;
                    q.push_front(f.first);
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    fin>>n>>m;
    st=1;
    d.resize(n+1,1e9);
    s.resize(n+1,2);
    a.resize(n+1);
    int na,nb,nc;
    for (int i=1;i<=m;i++) {
        fin>>na>>nb>>nc;
        a[na].push_back({nb,nc});
        ///a[nb].push_back({na,nc});
    }
    DEsopo(st);
    for (int i=2;i<=n;i++) {
        if (d[i]!=1e9) fout<<d[i]<<" ";
        else fout<<"0 ";
    }
    return 0;
}