#include<fstream.h>
ofstream g("dijkstra.out");
long v[5001][5001], i,j,n,m,p,viz[50001], t[50001], d[50001],x,y,c,a,nr;
 
long selmin()
{long min=1000001,b;
for(int k=1;k<=n;k++)
       if(!viz[k])
       if(d[k]<min)
        {min=d[k];
         b=k;
        }
return b;
}
 
 
 
 
int main()
{ifstream f("dijkstra.in");
 
f>>n>>m;
p=1;
for(i=1;i<=m;++i)
    {f>>x>>y>>c;
     v[x][y]=c;
     if(c==0) v[x][y]=-1;
     }
for(i=1;i<=n;++i)
    for(j=1;j<=n;j++)
        {if(i!=j && v[i][j]==0)
            v[i][j]=32000;
        if(v[i][j]==(-1)) v[i][j]=0;}
viz[p]=1;
for(i=1;i<=n;++i)
    {if(i!=p)t[i]=p;
     d[i]=v[p][i];
     }
nr=1;
while(nr<n)
    {a=selmin();
    viz[a]=1;nr++;
    for(i=1;i<=n;++i)
        if(!viz[i])
            if(d[a]+v[a][i]<d[i])
                {d[i]=d[a]+v[a][i];
                 t[i]=a;
                }
 
    }
for(i=2;i<=n;i++)
    if(d[i]==32000) g<<"0 ";
    else g<<d[i]<<' ';
g<<'\n';
 
f.close();
g.close();
return 0;
 
}