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

using namespace std;
typedef pair<int, int> pr;
const int N_MAX=50011;
const int oo=1<<29;

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;

void Dijkstra(int start, int N)
{
    pr x;
    fill(d, d+N+1, oo);
    fill(was, was+N+1, false);
    d[start]=0;
    for(pQ.push(pr(0, start)); !pQ.empty(); )
    {
        x=pQ.top(); pQ.pop();
        if(true == was[x.second])
            continue;
        was[x.second]=true;
        for(it=G[x.second].begin(), iend=G[x.second].end(); it < iend; ++it)
            if(d[it->first] > it->second + x.first)
            {
                d[it->first]=it->second+x.first;
                pQ.push(pr(d[it->first], it->first));
            }
    }
}
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));
    }
    Dijkstra(1, N);
    replace(d+1, d+N+1, oo, 0);
    copy(d+2, d+N+1, ostream_iterator<int>(out, " "));
    out<<"\n";

    return EXIT_SUCCESS;
}