#include<fstream>
#include<queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct qwerty{
    bool ok;
    int weight;
}x[111][111];
queue<int>q;
int z[111],i,j,n,m,a,b;
bool v[111];
void pr1(){
    while(!q.empty()){
        a=q.front();
        q.pop();
        v[a]=false;
        for(i=2;i<=n;i++)
            if(x[a][i].ok){
                if(z[i]==0){
                    z[i]=z[a]+x[a][i].weight;
                    q.push(i);
                    v[i]=true;
                }else{
                    if(z[i]<z[a]+x[a][i].weight)
                        if(v[i]==false){
                            q.push(i);
                            v[i]=true;
                        }
                }
            }
    }

}
int main(){
    z[1]=0;
    v[1]=true;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        fin>>a>>b,
        fin>>x[a][b].weight,
        x[a][b].ok=true;
    q.push(1);
    pr1();
    for(i=2;i<=n;i++)
        fout<<z[i]<<' ';
}