#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int INF=1.e20;

struct graf{
int x;
int cost;

};

vector<graf> a[50005];
int best[50005],c[50005];
int n,nodr;

void citire(){
    nodr=1;
int m;
f>>n>>m;
int y;
graf y1;
while(f>>y>>y1.x>>y1.cost){
    a[y].push_back(y1);

}

}
void dijkstra(int nod){

int i;
int p,u;
p=u=1;
c[1]=nod;
while(p<=u){

    for(i=0;i<a[c[p]].size();i++){
        if(best[a[c[p]][i].x]> a[c[p]][i].cost+best[c[p]]){

            best[a[c[p]][i].x] = a[c[p]][i].cost + best[c[p]];
            u++;
            c[u]=a[c[p]][i].x;


        }



    }


    p++;
}
for(i=2;i<=n;i++){
        if(best[i] == INF)g<<"0 ";
       else
        g<<best[i]<<" ";

}

}


int main()
{
    citire();
    for(int i=1;i<=n;i++)
        best[i]=INF;
    best[nodr]=0;

    dijkstra(nodr);

    return 0;
}