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

using namespace std;

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

struct Muchie {
    int nod, cost;

    bool operator< (const Muchie& x) const {
        return cost > x.cost;
    }
};

int n, m;
vector< pair<int, int> > v[50001];
priority_queue<Muchie> Q;
int d[50001];

void dijkstra(int source) {
    memset(d, 0x3f, sizeof d);
    d[source] = 0;
    Q.push({source, 0});
    int node, dist, currnode, currdist;
    while( Q.size() ) {
        node = Q.top().nod, dist = Q.top().cost;
        Q.pop();
        if( d[node] < dist )
            continue;
        for( const pair<int, int>& x: v[node] ) {
            currnode = x.first, currdist = x.second;
            if( d[currnode] > d[node] + currdist ) {
                d[currnode] = d[node] + currdist;
                Q.push({currnode, d[currnode]});
            }
        }
    }
}

void write() {
    for( int i = 2; i <= n; ++i ) {
        fout << (d[i] == 0x3f3f3f3f ? 0 : d[i]) << ' ';
    }
}

int main()
{
    fin >> n >> m;
    int x, y, c;
    for (; m; --m) {
        fin >> x >> y >> c;
        v[x].push_back({y, c});
    }
    dijkstra(1);
    write();
    return 0;
}