#include <stdio.h>
#include <iostream>
int n,m;
int rel1;
int rel2;
int val;
int b[50000][250000];
int c[50000][250000];
long int valo[50000];
bool viz[50000];
int minim()
{
    int mi=500000,pos;
    for(int i=1;i<=n;i++)
    {
        if(mi>valo[i]&&viz[i]==0)
        {
            mi=valo[i];
            pos=i;
        }
    }
    return pos;
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        fscanf(fin,"%d %d %d",&rel1,&rel2,&val);
        b[rel1][b[rel1][100]]=rel2;
        c[rel1][c[rel1][100]]=val;
        b[rel1][100]++;
        c[rel1][100]++;
        b[rel2][b[rel2][100]]=rel1;
        c[rel2][c[rel2][100]]=val;
        c[rel2][100]++;
        b[rel2][100]++;
    }
    for(int i=1;i<=n;i++) valo[i]=10000;
    valo[1]=1;
    int pos,counter=n-1;
    while(counter>=0)
    {
        counter--;
        pos=minim();
        std::cout<<pos<<"\n";
        for(int j=0;j<b[pos][100];j++)
        {
            std::cout<<valo[pos]+c[pos][j]<<" "<<valo[b[pos][j]]<<"\n";
            if(valo[pos]+c[pos][j]<valo[b[pos][j]])
            {
                valo[b[pos][j]]=valo[pos]+c[pos][j];
            }
        }
        viz[pos]=1;
    }
    for(int i=1;i<=n;i++)
    {
        fprintf(fout,"%d ",valo[i]);
    }
    system("pause");
}