1 /************************************************************** 2     Problem: 3624 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:60 ms 7     Memory:16416 kb 8 ****************************************************************/ 9  10 #include <cstdio>11  12 using namespace std;13 const int N = 20005;14 const int M = 100005;15 const int Maxlen = 15000010;16  17 struct edges {18     int x, y;19     edges() {}20     edges(int _x, int _y) : x(_x), y(_y) {}21 }e[M];22  23 int n, m, k, cnt;24 int fa[N];25 bool vis[M];26  27 char buf[Maxlen];28 int Len, Left;29  30 inline int read() {31     int x = 0;32     while (buf[Left] < ‘0‘ || ‘9‘ < buf[Left]) ++Left;33     while (‘0‘ <= buf[Left] && buf[Left] <= ‘9‘)34         x = x * 10 + buf[Left++] - ‘0‘;35     return x;36 }37    38 int len = 0, pr[15];39 inline void print(int x) {40     if (x < 0) putchar(‘-‘), x = -x;41     while (x)42         pr[++len] = x % 10, x /= 10;43     if (!len) putchar(‘0‘);44     while (len)45         putchar(pr[len--] + ‘0‘);46 }47  48  49 int find_fa(int x) {50     return fa[x] == x ? x : fa[x] = find_fa(fa[x]);51 }52  53 int main() {54     int i, x, y, f, L, R, fa1, fa2;55     Len = fread(buf, 1, Maxlen, stdin);56     buf[Len] = ‘ ‘;57     n = read(), m = read(), k = read();58     for (i = 1, L = 0, R = m + 1; i <= m; ++i) {59         x = read(), y = read(), f = read();60         if (f) e[++L] = edges(x, y);61         else e[--R] = edges(x, y);62     }63      64     for (i = 1; i <= n; ++i) fa[i] = i;65     for (i = 1; i <= m; ++i)66         if ((fa1 = find_fa(e[i].x)) != (fa2 = find_fa(e[i].y))) {67             fa[fa1] = fa2;68             if (i > L)69                 vis[i] = 1, cnt += 1;70         }71     if (cnt > k) {72         puts("no solution");73         return 0;74     }75      76     for (i = 1; i <= n; ++i) fa[i] = i;77     for (i = R; i <= m; ++i)78         if (vis[i]) fa[find_fa(e[i].x)] = find_fa(e[i].y);79     for (i = R; i <= m; ++i)80         if (!vis[i] && cnt < k && (fa1 = find_fa(e[i].x)) != (fa2 = find_fa(e[i].y))) {81             fa[fa1] = fa2, vis[i] = 1;82             ++cnt;83         }84     if (cnt != k) {85         puts("no solution");86         return 0;87     }88      89     for (i = 1; i <= L; ++i)90         if ((fa1 = find_fa(e[i].x)) != (fa2 = find_fa(e[i].y)))91             fa[fa1] = fa2, vis[i] = 1;92     for (i = 1; i <= m; ++i)93         if (vis[i]) {94             print(e[i].x), putchar(‘ ‘);95             print(e[i].y), putchar(‘ ‘);96             print(i <= L), putchar(‘\n‘);97         }98 }