# include <fstream>
# include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,i,x,y,z,l,t,c,w[50001],h[50001],p[50001];
vector<pair<int,int> > v[50001];
void read()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
         {
          f>>x>>y>>z;
          v[x].push_back(make_pair(y,z));
          w[x]=w[y]=50000001;
         }
}
void up_heap()
{
    t=c>>1;
    while(t>0&&w[h[t]]>w[h[c]])
          {
           swap(p[h[t]],p[h[c]]);
           swap(h[t],h[c]);
           c=t;
           t=c>>1;
          }
}
void down_heap()
{
    t=1;
    c=t<<1;
    c+=(c<l&&w[h[c]]>w[h[c+1]]);
    while(c<=l&&w[h[t]]>w[h[c]])
           {
            swap(p[h[t]],p[h[c]]);
            swap(h[t],h[c]);
            t=c;
            c=t<<1;
            c+=(c<l&&w[h[c]]>w[h[c+1]]);
           }
}
void Dijkstra()
{
    int d;
    w[1]=0;
    h[++l]=1;
    p[1]=l;
    while(l>0)
           {
            x=h[1];
            p[h[l]]=1;
            h[1]=h[l--];
            down_heap();
            d=v[x].size();
            for(i=0;i<d;i++)
                if(w[v[x][i].first]>w[x]+v[x][i].second)
                    {
                     w[v[x][i].first]=w[x]+v[x][i].second;
                     if(!p[v[x][i].first])
                         {
                          h[++l]=v[x][i].first;
                          p[v[x][i].first]=l;
                         }
                     c=p[v[x][i].first];
                     up_heap();
                    }
           }
}
void write()
{
    for(i=2;i<=n;i++)
         if(w[i]==50000001)
             g<<"0 ";
         else
           g<<w[i]<<" ";
}
int main()
{
    read();
    Dijkstra();
    write();
    f.close();
    g.close();
    return 0;
}