# include <fstream>
# include <set>
# define INF 1<<30
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,i,x,y,c,d[50001],t[50001],v[50001];
set<pair<int,int> > a[50001],b;
set<pair<int,int> >::iterator it;
void dijkstra()
{
    int z,mini,v[50001];
    for(i=1;i<=n;i++)
         {
          d[i]=INF;
          v[i]=0;
         }
    d[x]=0;
    b.insert(make_pair(x,0));
    v[x]++;
    while(b.size())
           {
            z=(*b.begin()).first;
            mini=(*b.begin()).second;
            b.erase((*b.begin()));
            if(v[z]==1)
                {
                 for(it=a[z].begin();it!=a[z].end();it++)
                      {
                       if(d[(*it).first]>d[z]+(*it).second)
                           {
                            d[(*it).first]=d[z]+(*it).second;
                            t[(*it).first]=z;
                            b.insert(make_pair((*it).first,d[(*it).second]));
                            v[(*it).first]++;
                           }
                      }
                }
            else
              v[z]--;
           }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
         {
          f>>x>>y>>c;
          a[x].insert(make_pair(y,c));
         }
    //f>>x>>y;
    x=1;
    dijkstra();
    for(i=2;i<=n;i++)
    g<<d[i]<<' ';
    /*while(t[y])
          {
           g<<t[y]<<" ";
           y=t[y];
          }*/
    f.close();
    g.close();
    return 0;
}