#include <fstream>
using namespace std;
const int inf=1<<30;
const int Nmax=2000;
int m,n,mat[Nmax][Nmax],V[Nmax],D[Nmax],T[Nmax];
void dijkstra(int ns)
{   int mini,nod,i,j,ok;
    for(i=1;i<=n;i++)
    {   D[i]=mat[ns][i];
        T[i]=ns;
    }
    V[ns]=1;ok=1;
    while(ok==1)
    {
        mini=inf;
        for(i=1;i<=n;i++)
        {  if(V[i]==0&&D[i]<mini)
            {   mini=D[i];
            nod=i;
            }

        }
        V[nod]=1;if(mini==inf)ok=0;
        else{
            for(i=1;i<=n;i++)
            {
                if(V[i]==0 && (D[nod]+mat[nod][i])<D[i])
                {   D[i]=D[nod]+mat[nod][i];
                    T[i]=nod;
                }
            }
        }
    }
}
int main()
{   int i,j,a,b,c;
    ifstream in("dijkstra.in");
    in>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        mat[i][j]=inf;
    for(i=1;i<=m;i++)
    {   in>>a>>b>>c;
        mat[a][b]=c;

    }
    dijkstra(1);
    ofstream out("dijkstra.out");
    for(i=2;i<=n;i++)
      if(D[i]==inf)out<<"0";
        else out<<D[i]<<" ";
    out<<"\n";
        //scoate_drum(3);
    return 0;

}