#include <bits/stdc++.h>
using namespace std;
#define NMAX 50005
#define INF 0x3f3f3f3f
vector<pair<int, int> > G[NMAX];
int d[NMAX],viz[NMAX];
int n,m,a,b,c;
struct cmp  {
    inline bool operator() ( const int i , const int j )
    {
        return d[i]>d[j] ;
    }
};
int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    f>>n>>m;
    for (int i=1;i<=m;i++) {
        f>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
    }

    memset(d,INF,sizeof(d));
    d[1] = 0;
    priority_queue <  int  , vector < int > , cmp > q ;
    q.push(1);
    while (!q.empty()) {
        int a=q.top();
        viz[a]=0;
        q.pop();

        for(int i=0;i<G[a].size();i++) {
            b=G[a][i].first;
            c=G[a][i].second;
            if (d[b]>d[a]+c) {
                d[b]=d[a]+c;
                if (!viz[b]) {
                    viz[b]=1;
                    q.push(b);
                }
            }
        }
    }

    for (int i=2;i<=n;i++) {
        if (d[i]==INF) {
            d[i]=0;
        }
        g<<d[i]<<' ';
    }
}