# include <fstream>
# include <vector>
# 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];
vector<int> b;
set<pair<int,int> > a[50001];
set<pair<int,int> >::iterator it;
void dijkstra()
{
    int z,mini;
    for(i=1;i<=n;i++)
         {
          d[i]=INF;
          //v[i]=0;
         }
    d[x]=0;
    b.push_back(x);
    //v[x]++;
    while(b.size())
           {
            z=*b.begin();
            b.erase(b.begin());
            if(true)
                {
                 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.push_back((*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++)
    if(d[i]!=INF)
    g<<d[i]<<' ';
    else g<<"0 ";
    /*while(t[y])
          {
           g<<t[y]<<" ";
           y=t[y];
          }*/
    f.close();
    g.close();
    return 0;
}