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

struct intpair{int x, y;};

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

vector<pair<int, int> > g[50005];
vector<pair<int, int> >:: iterator it;

intpair a[50005];
int n,m;

int getpozmin(){
    int i,mn=INT_MAX,p=1;
    for(i=2;i<=n;i++){
        if(a[i].x<=mn && a[i].y==0){
            mn=a[i].x;
            p=i;
        }
    }
    a[p].y=1;
    if(mn==INT_MAX)
        return 0;
    return p;
}

int main()
{
    int i,poz=1;
    a[1].x=0;
    fin>>n>>m;

    for(i=2;i<=n;i++){
        a[i].x=INT_MAX;
    }

    for(i=1;i<=m;i++){
        int x, y, c;
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }
    do{
        for(it=g[poz].begin();it!=g[poz].end();it++){
            if(it->second+a[poz].x < a[it->first].x){
                a[it->first].x=it->second+a[poz].x;
            }
        }
    }while(poz=getpozmin());

    for(i=2;i<=n;i++){
        fout<<a[i].x<<' ';
    }

    fin.close();
    fout.close();
    return 0;
}