#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;

const int oo=1<<30;
const int N_MAX=50000;
typedef pair<int, int> pr;

int d[N_MAX];
bool was[N_MAX];
vector<pr> G[N_MAX];
vector<pr>::const_iterator it, iend;
priority_queue<pr, vector<pr>, greater<pr> > pQ;

int main()
{
    int N, M, x, y, c;
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    for(in>>N>>M; M; --M)
    {
        in>>x>>y>>c;
        G[x].push_back(pr(y, c));
    }
    fill(d+1, d+N+1, oo);
    d[1]=0;
    for(pQ.push(pr(0, 1)); !pQ.empty();)
    {
        c=pQ.top().first;
        x=pQ.top().second;
        pQ.pop();
        if(true == was[x])
            continue;
        was[x]=true;
        for(it=G[x].begin(), iend=G[x].end(); it < iend; ++it)
            if(d[it->first] > d[x]+it->second)
            {
                d[it->first]=d[x]+it->second;
                pQ.push(pr(d[it->first], it->first));
            }
    }
    replace(d+1, d+N+1, oo, 0);
    copy(d+2, d+N+1, ostream_iterator<int>(out, " "));

    return 0;
}