#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int nmax= 50000;
const int inf= 1<<30;

struct Pair {
    int x, y;

    Pair(int a, int b) : x {a}, y {b} {};
};

struct PairCompare {
    bool operator() ( const Pair &lhs, const Pair &rhs ) {
        return lhs.y>rhs.y;
    }
};

bool u[nmax+1];
int d[nmax+1];
vector <Pair> v[nmax+1];

void dijkstra( int x ) {
    d[x]= 0;
    priority_queue <Pair, vector<Pair>, PairCompare> q;
    for ( q.push(Pair(x, 0)); !q.empty(); ) {
        auto x= q.top();
        q.pop();
        u[x.x]= 0;

        for ( auto it: v[x.x] ) {
            if ( d[x.x]+it.y<d[it.x] ) {
                d[it.x]= d[x.x]+it.y;
                if ( u[it.x]==0 ) {
                    u[it.x]= 1;
                    q.push(it);
                }
            }
        }
    }
}

int main() {
    int n, m;
    fin>>n>>m;
    for ( int i= 0, x, y, z; i<m; ++i ) {
        fin>>x>>y>>z;

        v[x].push_back(Pair(y, z));
    }

    for ( int i= 1; i<=n; ++i ) {
        d[i]= inf;
    }
    dijkstra(1);

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

        fout<<d[i]<<" ";
    }
    fout<<"\n";

    return 0;
}