#include <fstream>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int inf=1<<30;
int m,n,mat[20000][20000],viz[50000],d[50000],ok,j,mini;
/*struct lista
{   int v;
    int c;
    lista *urm;


};
lista *nou,*cap[50001];
*/
void dijkstra(int ns)
{   int i,nod;
    viz[ns]=1;
    for(i=1;i<=n;i++)
    {  if(viz[i]==0)
         d[i]=mat[ns][i];
    }
    d[ns]=0;

    ok=0;
    while(ok==0)
    {   mini=inf;
        for(i=1;i<=n;i++)
        {  if(viz[i]==0)
            if(mini>d[i])
            {mini=d[i];
                nod=i;
            }
        }
    viz[nod]=1;
    if(mini==inf) ok=1;
    else
    {   for(i=1;i<=n;i++)
    {   if(viz[i]==0)
        if(d[i]>mat[nod][i]+mini)
        {   d[i]=mat[nod][i]+mini;

        }

    }

    }
    }


}
int main()
{   int a,b,c,i;
    in>>n>>m;
   /* for(i=1;i<=m;i++)
    {   in>>a>>b>>c;
        nou=new lista;
        nou->v=b;
        nou->c=c;
        nou->urm=cap[a];
        cap[a]=nou;

    }
    */
    for(i=1;i<=m;i++)
    {   in>>a>>b>>c;
        mat[a][b]=c;
        if(c==0)   mat[a][b]=-1;
    }
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {   if(mat[i][j]==0)
        mat[i][j]=inf;
        if(mat[i][j]==-1)
            mat[i][j]=0;

    }


    dijkstra(1);
    for(i=2;i<=n;i++)
        if(d[i]==inf) out<<0<<" ";
    else
        out<<d[i]<<" ";
    return 0;
}