import java.io.* ;
import java.util.* ;

class Arete {
    int g,d,p ;
    Arete(int g, int d, int p) {
        this.g=g; this.d=d; this.p=p; }
}

public class Kruskal {
    final static int nNoeuds = 50 ;
    final static int nAretes = nNoeuds * nNoeuds ;

    static Arete [] graphe = new Arete [nAretes] ; // le graphe de depart
    static Arete [] arbre = new Arete [nNoeuds];  // l'arbre final sous
                                                  // forme de graphe

    static int [] papa = new int [nNoeuds] ;    // l'arbre sous forme de
                                                // tableau des peres

    static void init (int[] t) {              // initialisation des
        for (int i=0; i<t.length; i++)        // peres a -1
            t[i]=-1 ;
    }

    static void triGraph (Arete [] t, int l) {   // tri tout simple
        int j; int k;
        Arete a;
        for (int i=0; i<l; i++) {
            j=i;
            for (k=j; k<l; k++)
                if (t[k].p<t[j].p)
                    j=k;
            a=t[j];
            t[j]=t[i];
            t[i]=a;
        }
        return;
    }


    static int lit ()  {          // lecture d'un entier au clavier
        int s;
        BufferedReader in = 
            new BufferedReader(new InputStreamReader(System.in));
        try {
            s = Integer.parseInt(in.readLine());
        }
        catch (IOException e) {
            s = 0 ;
        }
        return s;
    }



    // on verifie si deux noeuds sont deja relies dans les arbres courants
    // si c'est non, on relie les deux arbres en plus
    static boolean cyclep (int[] t, int a, int b) {
        int i=a; int j=b;
        while (t[i]>0) 
            i=t[i];
        while (t[j]>0) 
            j=t[j];
        if (i!=j) t[i]=j;
        return i!=j;
    }

    // l'algo de kruskal
    // a chaque etape, on enrichie le graphe courant en plus
    static boolean kruskal (Arete [] g, int nn, int na, int [] a, 
                            Arete [] arbre) {
        init(a);
        int ia = 0;
        int nb = 0;
        while (ia<na && nb < nn ){
            if (cyclep(a,g[ia].g,g[ia].d)) {
                arbre[nb]=g[ia];
                nb++;
            }
            ia++;
                
        }
        return nb==nn-1;
    }


    // lit un ensemble d'aretes au clavier
    static int litGraph (Arete [] g) {
        int i = 0;
        int a; int b; int p=1 ;
        while (p>0) {
            System.out.print("Noeud 1 ?");
            a=lit();
            System.out.println("");
            System.out.print("Noeud 2 ?");
            b=lit();
            System.out.println("");
         
            System.out.print("poids ? (0 pour finir)");
            p=lit();
            System.out.println("");
            if (p>0) {
                g[i] = new Arete(a,b,p);
                i++;
            }
        }
        return(i);
    }

    // affichage primaire d'un graphe
    static void affGraph (Arete [] g, int n) {
        System.out.println("");
        for (int j=0; j<n; j++) {
            System.out.print(j);
            if (g[j]!=null)
                System.out.println(" "+g[j].g+" "+g[j].d+" "+g[j].p);
        }
    }
            

    public static void main (String[] args) {
        int nn ; int na;
        System.out.print("nombre de noeuds ?");
        nn=lit() ;
        na = litGraph(graphe) ;
        triGraph(graphe,na);
        kruskal(graphe,nn,na,papa,arbre);
        affGraph(arbre,nn-1);
    }
        

}