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

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct abc{
    int nod, cost;
    bool operator < (const abc& a)const
    {
        return cost > a.cost;
    }
};

abc mp(int n, int c){
    abc t;
    t.nod=n;
    t.cost=c;
    return t;
}




int n, m, a, b, c, x, y;
int dist[10000];

vector <abc> v[10000];
priority_queue <abc> q;



int main()
{
    in>>n>>m;
    for(int i=2;i<=n;i++)dist[i]=1<<30;
    for(int i=1;i<=m;i++){
        in>>a>>b>>c;
        v[a].push_back(mp(b, c));
    }

    q.push(mp(1, 0));
    while(!q.empty()){
        x=q.top().nod;
        y=q.top().cost;
        q.pop();
        if(y!=dist[x])continue;
        for(auto i:v[x]){
            if(dist[i.nod]>dist[x]+i.cost){
                dist[i.nod]=dist[x]+i.cost;
                q.push(mp(i.nod, dist[i.nod]));
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(dist[i]==1<<30)dist[i]=0;

        out<<dist[i]<<" ";
    }


    return 0;
}