#include <bits/stdc++.h>

const int inf=2e9+3;
const int nmax=5e4+3;

bool f[nmax];

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>v[n+3];
    for(int i=1;i<=m;i++)
    {
      int x,y,k;
      cin>>x>>y>>k;
      v[x].push_back(make_pair(y,k));
    }
    vector<int>d(n+3,inf),p(n+3);
    d[1]=0;
    set<pair<int,int>>h;
    h.insert(make_pair(1,0));
    while(!h.empty())
    {
      int k=h.begin()->first;
      h.erase(h.begin());
      f[k]=1;
      for(auto it:v[k])
      {
        int kk=it.first;
        int cc=it.second;
        if(d[k]+cc<d[kk])
        {
          if(d[kk]!=inf) h.erase(make_pair(kk,d[kk]));
          d[kk]=d[k]+cc;
          p[kk]=k;
          h.insert(make_pair(kk,d[kk]));
        }
      }
    }
    for(int i=2;i<=n;i++)
    if(d[i]==inf) cout<<"0 "; else cout<<d[i]<<" ";

}