#include <fstream>
#include <vector>
#include <queue>
#define INF 333000000
using namespace std;
int main()
{
    vector<pair<long, long> > *graf;
    queue<long> que;
    long *dist;
    bool *inque;
    long n, m, aux1, aux2, aux3, nod;
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    in>>n>>m;
    graf = new vector<pair<long, long> >[n+1];
    dist = new long[n+1];
    inque = new bool[n+1];
    for(long i=1; i<=m; ++i)
    {
        in>>aux1>>aux2>>aux3;
        graf[aux1].push_back(make_pair(aux2, aux3));
    }
    for(long i=1; i<=n; ++i)
    {
        dist[i]=INF;
        inque[i]=false;
    }
    que.push(1);
    inque[1]=true;
    dist[1]=0;
    while(!que.empty())
    {
        nod=que.front();
        que.pop();
        inque[nod]=false;
        for(vector<pair<long, long> >::iterator it=graf[nod].begin(), ed=graf[nod].end(); it!=ed; ++it)
            if(dist[nod]+(*it).second<dist[(*it).first])
            {
                dist[(*it).first]=dist[nod]+(*it).second;
                if(!inque[(*it).first])
                {
                    inque[(*it).first]=true;
                    que.push((*it).first);
                }
            }
    }
    for(long i=2; i<=n; ++i)
    {
        if(dist[i]==INF) out<<"0 ";
        else out<<dist[i]<<' ';
    }
    in.close(); out.close();
    return 0;
}