#include <fstream>
#include <vector>
#include <climits>
using namespace std;
struct muchie{
    int x,c;
};
int n,m,a,b,cost,i,j,d[1001];
vector <muchie> v[10001];
int main(){

    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>a>>b>>cost;
        v[a].push_back({b,cost});
        if(a==1)
            d[b]=cost;
    }
    for(i=2;i<=n;i++)
        if(d[i]==0)
            d[i]=INT_MAX;
    viz[1]=1;
    p=1;
    for(i=1;i<=n-1;i++){
        Min=INT_MAX;
        for(j=1;j<=n;j++)
            if(viz[j]==0 && d[j]<Min){
                Min=d[j];
                p=j;
        }
        viz[p]=1;
        //actualizare distante
        for(j=1;j<=n;j++)
            if(viz[j]==0 && d[j]>d[p]+v[p][j].c)
                d[j]=d[p]+v[j][p].c;

    }
    for(i=2;i<=n;i++)
        cout<<d[i]<<" ";

    return 0;
}