prim

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <stdlib.h>
#include <stdio.h>
#include <queue>

#define LL long long
#define ULL unsigned LL
#define For(i, b) for(int i=0; i<b; i++)

using namespace std;

int val[400009], next[400009], weight[400009], last;
bool vertHash[20009];
priority_queue<pair<int, int> > pq_next;

void initList(int numVertex){
    For(i, numVertex)
        val[i+1] = i+1;
    last = numVertex+1;
}

void newEdge(int v1, int v2, int w){
    next[val[v1]] = last;
    val[last] = v2;
    weight[last] = w;
    val[v1] = last;
    last++;
}

void addEdge(int v1, int v2, int w){
    newEdge(v1, v2, w);
    newEdge(v2, v1, w);
}

void markVis(int a){
    vertHash[a] = 1;
    cout<<a<<endl;
}

bool vertVis(int a){
    return vertHash[a];
}

void addNextEdges(int a){
    int curInd, curWeig;
    int nxt = next[a];
    while (nxt != 0){
        curInd = val[nxt];
        curWeig = weight[nxt];
        if(!vertVis(curInd))
            pq_next.push(make_pair(-1 * curWeig, curInd ));
        nxt = next[nxt];
    }
}

int numVertex, numEdge;

int main(){
    freopen("input.in.c", "r", stdin);

    cin>>numVertex>>numEdge;

    initList(numVertex);

    int tm1, tm2, tmw;
    For(i, numEdge)
        cin>>tm1>>tm2>>tmw, addEdge(tm1, tm2, tmw);

    /*For(i, 20){
        cout<<i<<" "<<val[i]<<" "<<weight[i]<<" "<<next[i]<<endl;
    }*/

    const int START_VERTEX = 1;
    int numTreeVert = 0;
    markVis(START_VERTEX);
    pq_next.push(make_pair(0, START_VERTEX));

    while(numTreeVert < numVertex){
        int edgeDest = pq_next.top().second, edgeWeig=pq_next.top().first;
        pq_next.pop();

        numTreeVert++;
        markVis(edgeDest);
        addNextEdges(edgeDest);
    }

    return 0;
}