#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
#define NMAX 50005
#define inf 0x3f3f3f3f
using namespace std;
struct Servus
{
    int nod,cost;
    bool operator <(const Servus& a)const
    {
        return cost>a.cost;
    }
};
Servus makepair(int a,int b)
{
    Servus n;
    n.nod=a;
    n.cost=b;
    return n;
}

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

int n,m;
int dist[NMAX];
vector<Servus> v[NMAX];
priority_queue<Servus> q;
void dickstra(int nod)
{
    dist[nod]=0;
    q.push(makepair(nod,0));
    while(!q.empty()){
        int fata=q.top().nod;
        int frumoasa=q.top().cost;
        q.pop();
        if(frumoasa!=dist[fata])continue;
        for(auto i:v[fata]){
            if(dist[i.nod]>dist[fata]+i.cost){
                dist[i.nod]=dist[fata]+i.cost;
                q.push(makepair(i.nod,dist[i.nod]));
            }
        }
    }
}
int main()
{
    int a,b,c;
    in>>n>>m;
    for(int i=1;i<=m;++i){
        in>>a>>b>>c;
        v[a].push_back(makepair(b,c));
    }
    memset(dist,0x3f3f3f3f,sizeof dist);
    dickstra(1);
    for(int i=2;i<=n;++i){
        if(dist[i]==inf)
            dist[i]=0;
        out<<dist[i]<<" ";
    }
    return 0;
}