#include <iostream>
#include <fstream>

using namespace std;

struct node{
    int cost;
    int prevN;
} nod[100];

int N,M,m[1000][1000],Start = 1;
int parcurs[1000], stiva[1000][3], kstiva, kparcurs;

void citire(){
    int a,b,c;
    ifstream in ("dijkstra.in");
    in>>N>>M;
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            m[i][j] = 0;
    for (int i=1;i<=M;i++){
        in>>a>>b>>c;
        m[a][b] = c;
    }
    for (int i=1;i<=N;i++)
        nod[i].cost = -1;
    nod[Start].cost = 0;
    stiva[1][1] = Start;
    stiva[1][2] = 0;
    kstiva = 1;
    kparcurs = 0;

    in.close();

}

void rem(int a){

    int poz;
    for (poz=1;stiva[poz][1]!=a;poz++);

    for (int i=poz+1;i<=kstiva;i++){
        stiva[i-1][1] = stiva [i][1];
        stiva[i-1][2] = stiva [i][2];
    }
    kstiva--;
}

int in_stiva (int a){
    for (int i=1;i<=kstiva;i++)
        if (stiva[i][1] == a) return 1;
    return 0;
}

int gata (int a){
    for (int i=1;i<=kparcurs;i++)
        if (parcurs[i] == a)
            return 1;
    return 0;
}

void Dijkstra(){

    int cur_nod, a;
    while (kparcurs != N){

        cur_nod = stiva[1][1];

        for (int i=1;i<=N;i++){ /// cautam toate posibilitatile si le salvam in stiva

                if (m[cur_nod][i] > 0){
                    a = nod[cur_nod].cost + m[cur_nod][i];
                    if (!gata(i)){
                        if (!in_stiva(i)){
                            kstiva++;
                            stiva[kstiva][1] = i;
                            stiva[kstiva][2] = a;
                            nod[i].cost = stiva[kstiva][2];
                            nod[i].prevN = cur_nod;
                        }
                        else if (in_stiva(i) && nod[i].cost > a){
                            nod[i].cost = a;
                            nod[i].prevN = cur_nod;
                            stiva[kstiva][1] = i;
                            stiva[kstiva][2] = a;
                        }
                    }
                }

        }

        rem(cur_nod);                  /// scoatem primul element din stiva
        kparcurs++;
        parcurs[kparcurs] = cur_nod;
    }





}

int main()
{
    citire();
    Dijkstra();

    ofstream out ("dijkstra.out");
    for (int i=2;i<=N;i++)
        out<<i<<" "<<nod[i].cost<<"\n";
        out.close();

    return 0;
}