#include <fstream>
#include<vector>
#include<set>
#define inf 500000000

using namespace std;
vector< pair<int,int> >v[50001];
multiset < pair<int,int> > s;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,i,j,x,y,c,d[50001];
int main()
{
f>>n>>m;
for(i=1;i<=m;i++){
    f>>x>>y>>c;
    v[x].push_back(make_pair(y,c));
}
for(i=1;i<=n;i++)
    d[i]=inf;
d[0]=0;
s.insert(make_pair(0,1));
for(i=j;j<n&&!s.empty();j++)
{
    multiset <pair <int, int> > :: iterator it = s.begin() ;
    int nod=(*it).second;
    int cost=(*it).first;
    s.erase(it);
    for(i=0;i<v[nod].size();i++){
      int vec=  v[nod][i].first;
      int ct=v[nod][i].second;

         if(d[vec]>cost+ct)
    {
        d[vec]=cost+ct;

        s.insert(make_pair(d[vec],vec));
    }
    }
}
for(i=2;i<=n;i++)
      if(d[i]==inf)
       g<<i<<" ";
else
    g<<d[i]<<" ";
    return 0;
}