#include <bits/stdc++.h>
#define N 100005

using namespace std;

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

int n,m,x,y,c;

int main()
{
    fin>>n>>m;
    vector<vector<pair<int,int> > > G(n+5, vector<pair<int,int> >(1, {0,0}));
    for(int i=1; i<=m; ++i)
    {
        fin>>x>>y>>c;
        G[x].push_back({y,c});
    }
    vector<bool> f(n+5,0);
    vector<int> d(n+5,1e9);
    for(auto it=G[1].begin(); it!=G[1].end(); ++it)
        d[it->first]=it->second;
    f[1]=1,d[1]=0;
    d[0]=1e9,f[0]=1;
    for(int k=1; k<n; ++k)
    {
        int pmax=0;
        for(int i=1; i<=n; ++i)
            if(f[i]==0&&d[pmax]>d[i])
                pmax=i;
        if(pmax>-1)
        {
            f[pmax]=1;
            for(auto it=G[pmax].begin(); it!=G[pmax].end(); ++it)
                if(f[it->first]==0&&d[it->first]>d[pmax]+it->second)
                    d[it->first]=d[pmax]+it->second;
        }
    }
    for(int i=2; i<=n; ++i)
        if(d[i]==1e9) fout<<"0 ";
        else fout<<d[i]<<' ';
    return 0;
}