#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

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() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d",&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++) {
        scanf("%d %d %d",&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) printf("%d ", d[i]);
        else printf("%d ", 0);
    }
    return 0;
}