#include <fstream>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

#define nmax 50001

int n,m,viz[nmax],d[nmax],vf,vfm;
long long c[10000][10000];

int main()
{
    fin>>n;fin>>m;
    int i,j,a,b,inf;
    for( i=1; i<=n ;i++ )
        {fin>>a>>b>>inf;
        c[a][b]=inf;}
    vf=1;
    for(i=1;i<=n;i++)
        d[i]=c[vf][i];
    viz[vf]=1;
    for(i=1;i<=n-1;i++)
        {vfm=0;
        for( j=1;j<=n;j++)
            if(viz[j]==0&&d[i]!=0)
                if(vfm==0||d[j]<d[vfm])
                    vfm=j;
        viz[vfm]=1;
        for( j=1;j<=n;j++)
            if(viz[j]==0&&c[vfm][j]!=0)
                if(d[j]==0||d[vfm]+c[vfm][j]<d[j])
                    d[j]=d[vfm]+c[vfm][j];
        if(d[i]!=0)
        fout<<d[i]<<" ";
        if(vfm!=0)
            fout<<vfm<<" ";
        }

    return 0;
}