#include<fstream>
using namespace std;
#include<vector>
#define inf 100000
long n, m;
 
int main(){
 
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
     
    fin >> n >> m;
    vector<long> a(m+1,0), b(m+1, 0), c(m+1,0);
    vector<long> drum(n+1, inf);
    for(int i=1; i<=m; i++){
        fin >> a[i] >> b[i] >> c[i];
        if(a[i] == 1){
            drum[b[i]] = c[i];
        }
    }
     
     
    bool ok;
    do{
         
        ok = false;
        for(int i=1; i<=m; i++){
            if(drum[b[i]] > drum[a[i]] + c[i])
                drum[b[i]] = drum[a[i]] + c[i], ok=true;
        }
     
     
    }while(ok);
     
         
    for(int i=2; i<=n; i++){
        if(drum[i] == inf) fout << "0 ";
        else fout<< drum[i] << " ";
    }
 
    return 0;
}