#include <bits/stdc++.h>
#define ll long long
#define make(type,x) type x; cin>>x
#define make2(type,x,y) type x,y; cin>>x>>y
#define fr(x,y) for(long long x=0;x<y;x++)
#define INF (ll) 1e18
 
# define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)
 
using namespace std;
 
ll n,m;
ll N=1e5+5;
vector <vector <pair <ll,ll> > >vec(N);
vector <ll> d(N,INF);
struct comp{
    bool operator() (const ll &a, const ll &b) const{
        return d[a]<d[b];
    }
 
};
int main(){
    IOS;
    cin>>n>>m;
    fr(i,m){
        make2(ll,x,y); make(ll,len);
        vec[--x].push_back({--y,len});
    }
    d[0]=0;
    set <ll,comp> q;
    q.insert(0);
    while(!q.empty()){
        ll e=*q.begin(); q.erase(q.begin());
        for(auto x : vec[e]){
            ll to=x.first; ll len=x.second;
            if(d[e]+len<d[to]){
                q.erase(to);
                d[to]=d[e]+len;
                q.insert(to);
            }
        }
    }
    fr(i,n) cout<<d[i]<<" ";
    cout<<endl;
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgbWFrZSh0eXBlLHgpIHR5cGUgeDsgY2luPj54CiNkZWZpbmUgbWFrZTIodHlwZSx4LHkpIHR5cGUgeCx5OyBjaW4+Png+PnkKI2RlZmluZSBmcih4LHkpIGZvcihsb25nIGxvbmcgeD0wO3g8eTt4KyspCiNkZWZpbmUgSU5GIChsbCkgMWUxOAogCiMgZGVmaW5lIElPUyBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZShOVUxMKQogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKbGwgbixtOwpsbCBOPTFlNSs1Owp2ZWN0b3IgPHZlY3RvciA8cGFpciA8bGwsbGw+ID4gPnZlYyhOKTsKdmVjdG9yIDxsbD4gZChOLElORik7CnN0cnVjdCBjb21wewogICAgYm9vbCBvcGVyYXRvcigpIChjb25zdCBsbCAmYSwgY29uc3QgbGwgJmIpIGNvbnN0ewogICAgICAgIHJldHVybiBkW2FdPGRbYl07CiAgICB9CiAKfTsKaW50IG1haW4oKXsKICAgIElPUzsKICAgIGNpbj4+bj4+bTsKICAgIGZyKGksbSl7CiAgICAgICAgbWFrZTIobGwseCx5KTsgbWFrZShsbCxsZW4pOwogICAgICAgIHZlY1stLXhdLnB1c2hfYmFjayh7LS15LGxlbn0pOwogICAgfQogICAgZFswXT0wOwogICAgc2V0IDxsbCxjb21wPiBxOwogICAgcS5pbnNlcnQoMCk7CiAgICB3aGlsZSghcS5lbXB0eSgpKXsKICAgICAgICBsbCBlPSpxLmJlZ2luKCk7IHEuZXJhc2UocS5iZWdpbigpKTsKICAgICAgICBmb3IoYXV0byB4IDogdmVjW2VdKXsKICAgICAgICAgICAgbGwgdG89eC5maXJzdDsgbGwgbGVuPXguc2Vjb25kOwogICAgICAgICAgICBpZihkW2VdK2xlbjxkW3RvXSl7CiAgICAgICAgICAgICAgICBxLmVyYXNlKHRvKTsKICAgICAgICAgICAgICAgIGRbdG9dPWRbZV0rbGVuOwogICAgICAgICAgICAgICAgcS5pbnNlcnQodG8pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgZnIoaSxuKSBjb3V0PDxkW2ldPDwiICI7CiAgICBjb3V0PDxlbmRsOwogICAgcmV0dXJuIDA7Cn0=

MyA0CjEgMiA2CjEgMyAyCjMgMiAzCjEgMyA0

3 4
1 2 6
1 3 2
3 2 3
1 3 4