#include <bits/stdc++.h>
const int MAXN = 1e3 + 3;
const int MAXM = 2e3 + 3;
const int LEN = 1 << 11;
inline int read() {
int x = 0; bool f = 1; register char c = getchar();
for(; !std::isdigit(c); c = getchar()) f ^= c == '-';
for(; std::isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? x : -x;
}
int n, m, u[MAXM], v[MAXM], dis[MAXN], times[MAXN];
bool inq[MAXN], vis1[MAXN], visn[MAXN];
int fa[MAXN];
inline int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
int a = find(x), b = find(y);
if(a == b) return ;
fa[a] = b;
}
struct Edges {
int to, dis, nxt;
Edges() {}
Edges(int to, int dis, int nxt): to(to), dis(dis), nxt(nxt) {}
} edge[MAXM << 1];
int head[MAXN];
inline void addEdge(int u, int v, int d) {
static int cnt = 0;
edge[++cnt] = Edges(v, d, head[u]);
head[u] = cnt;
}
std::vector<int> G[MAXN], nG[MAXN];
inline void addEdge(int u, int v, std::vector<int> ver[]) {
ver[u].push_back(v);
}
void dfs(int x) {
int size = G[x].size();
for(int i = 0; i < size; ++i) {
int to = G[x][i];
if(vis1[to]) continue;
vis1[to] = 1; dfs(to);
}
}
void nDfs(int x) {
int size = nG[x].size();
for(int i = 0; i < size; ++i) {
int to = nG[x][i];
if(visn[to]) continue;
visn[to] = 1; nDfs(to);
}
}
struct Queue {
int l, r, q[LEN + 10];
Queue(): l(1), r(0) {}
inline void push(int x) { q[++r & (LEN - 1)] = x; }
inline void pop() { ++l; }
inline int front() { return q[l & (LEN - 1)]; }
inline bool empty() { return l > r; }
};
inline bool SPFA(int s) {
std::memset(dis, 0x3f, sizeof dis);
dis[s] = 0; inq[s] = 1; times[s] = 1;
Queue q; q.push(s);
while(!q.empty()) {
int u = q.front(); q.pop();
inq[u] = 0;
for(int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if(dis[u] + edge[i].dis < dis[v]) {
dis[v] = dis[u] + edge[i].dis;
if(++times[v] > n) return 0;
if(!inq[v]) q.push(v), inq[v] = 1;
}
}
}
return 1;
}
signed main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i) fa[i] = i;
for(int i = 1; i <= m; ++i) {
u[i] = read(), v[i] = read();
addEdge(u[i], v[i], G), addEdge(v[i], u[i], nG);
merge(u[i], v[i]);
}
/*
并查集判断 1 和 n 是否联通(其实没啥用
nG[] 存反边 ==> n -> 1
G[] 存正向边 ==> 1 -> n
*/
if(find(1) != find(n)) {
puts("-1");
return 0;
}
dfs(1); nDfs(n);
static bool flag[MAXN] = {0};
for(int i = 1; i <= n; ++i) if(vis1[i] && visn[i]) flag[i] = 1;
if(!vis1[n]) {
puts("-1");
return 0;
}
flag[1] = flag[n] = 1;
/*
注意这里是判断 1 到 n 中每个点是否在答案路径上,枚举的是 1 ~ n
vis1[] 是从 1 到 n 上经过的点
visn[] 是从 n 到 1 上经过的点
因为是有向边,所以要判断一下 1 可不可以到 n
比如:
3 2
3 1
1 2
ans: -1
*/
for(int i = 1; i <= m; ++i)
if(flag[u[i]] && flag[v[i]]) addEdge(u[i], v[i], 9), addEdge(v[i], u[i], -1);
if(!SPFA(1)) {
puts("-1");
return 0;
}
/*
只对答案路径上的点建边,跑差分约束
如果出现负环,差分约束系统无解。
*/
printf("%d %d\n", n, m);
for(int i = 1; i <= m; ++i) {
printf("%d %d ", u[i], v[i]);
if(flag[u[i]] && flag[v[i]]) printf("%d\n", dis[v[i]] - dis[u[i]]);
else puts("1"); //随便输出啥,反正无用边不影响
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgpjb25zdCBpbnQgTUFYTiA9IDFlMyArIDM7CmNvbnN0IGludCBNQVhNID0gMmUzICsgMzsKY29uc3QgaW50IExFTiA9IDEgPDwgMTE7CgppbmxpbmUgaW50IHJlYWQoKSB7CglpbnQgeCA9IDA7IGJvb2wgZiA9IDE7IHJlZ2lzdGVyIGNoYXIgYyA9IGdldGNoYXIoKTsKCWZvcig7ICFzdGQ6OmlzZGlnaXQoYyk7IGMgPSBnZXRjaGFyKCkpIGYgXj0gYyA9PSAnLSc7Cglmb3IoOyBzdGQ6OmlzZGlnaXQoYyk7IGMgPSBnZXRjaGFyKCkpIHggPSB4ICogMTAgKyAoYyBeIDQ4KTsKCXJldHVybiBmID8geCA6IC14Owp9CgppbnQgbiwgbSwgdVtNQVhNXSwgdltNQVhNXSwgZGlzW01BWE5dLCB0aW1lc1tNQVhOXTsgCmJvb2wgaW5xW01BWE5dLCB2aXMxW01BWE5dLCB2aXNuW01BWE5dOwoKaW50IGZhW01BWE5dOwoKaW5saW5lIGludCBmaW5kKGludCB4KSB7CglyZXR1cm4gZmFbeF0gPT0geCA/IHggOiBmYVt4XSA9IGZpbmQoZmFbeF0pOwp9CmlubGluZSB2b2lkIG1lcmdlKGludCB4LCBpbnQgeSkgewoJaW50IGEgPSBmaW5kKHgpLCBiID0gZmluZCh5KTsKCWlmKGEgPT0gYikgcmV0dXJuIDsKCWZhW2FdID0gYjsKfQoKc3RydWN0IEVkZ2VzIHsKCWludCB0bywgZGlzLCBueHQ7CglFZGdlcygpIHt9CglFZGdlcyhpbnQgdG8sIGludCBkaXMsIGludCBueHQpOiB0byh0byksIGRpcyhkaXMpLCBueHQobnh0KSB7fQp9IGVkZ2VbTUFYTSA8PCAxXTsKCmludCBoZWFkW01BWE5dOwoKaW5saW5lIHZvaWQgYWRkRWRnZShpbnQgdSwgaW50IHYsIGludCBkKSB7CglzdGF0aWMgaW50IGNudCA9IDA7CgllZGdlWysrY250XSA9IEVkZ2VzKHYsIGQsIGhlYWRbdV0pOwoJaGVhZFt1XSA9IGNudDsKfQoKc3RkOjp2ZWN0b3I8aW50PiBHW01BWE5dLCBuR1tNQVhOXTsKaW5saW5lIHZvaWQgYWRkRWRnZShpbnQgdSwgaW50IHYsIHN0ZDo6dmVjdG9yPGludD4gdmVyW10pIHsKCXZlclt1XS5wdXNoX2JhY2sodik7Cn0KCnZvaWQgZGZzKGludCB4KSB7CglpbnQgc2l6ZSA9IEdbeF0uc2l6ZSgpOwoJZm9yKGludCBpID0gMDsgaSA8IHNpemU7ICsraSkgewoJCWludCB0byA9IEdbeF1baV07CgkJaWYodmlzMVt0b10pIGNvbnRpbnVlOwoJCQoJCXZpczFbdG9dID0gMTsgZGZzKHRvKTsKCX0KfQp2b2lkIG5EZnMoaW50IHgpIHsKCWludCBzaXplID0gbkdbeF0uc2l6ZSgpOwoJZm9yKGludCBpID0gMDsgaSA8IHNpemU7ICsraSkgewoJCWludCB0byA9IG5HW3hdW2ldOwoJCWlmKHZpc25bdG9dKSBjb250aW51ZTsKCQkKCQl2aXNuW3RvXSA9IDE7IG5EZnModG8pOwoJfQp9CgpzdHJ1Y3QgUXVldWUgewoJaW50IGwsIHIsIHFbTEVOICsgMTBdOwoJUXVldWUoKTogbCgxKSwgcigwKSB7fQoJCglpbmxpbmUgdm9pZCBwdXNoKGludCB4KSB7IHFbKytyICYgKExFTiAtIDEpXSA9IHg7IH0KCWlubGluZSB2b2lkIHBvcCgpIHsgKytsOyB9CglpbmxpbmUgaW50IGZyb250KCkgeyByZXR1cm4gcVtsICYgKExFTiAtIDEpXTsgfQoJaW5saW5lIGJvb2wgZW1wdHkoKSB7IHJldHVybiBsID4gcjsgfQp9OwoKaW5saW5lIGJvb2wgU1BGQShpbnQgcykgewoJc3RkOjptZW1zZXQoZGlzLCAweDNmLCBzaXplb2YgZGlzKTsKCWRpc1tzXSA9IDA7IGlucVtzXSA9IDE7IHRpbWVzW3NdID0gMTsKCVF1ZXVlIHE7IHEucHVzaChzKTsKCQoJd2hpbGUoIXEuZW1wdHkoKSkgewoJCWludCB1ID0gcS5mcm9udCgpOyBxLnBvcCgpOwoJCWlucVt1XSA9IDA7CgkJZm9yKGludCBpID0gaGVhZFt1XTsgaTsgaSA9IGVkZ2VbaV0ubnh0KSB7CgkJCWludCB2ID0gZWRnZVtpXS50bzsKCQkJaWYoZGlzW3VdICsgZWRnZVtpXS5kaXMgPCBkaXNbdl0pIHsKCQkJCWRpc1t2XSA9IGRpc1t1XSArIGVkZ2VbaV0uZGlzOwoJCQkJaWYoKyt0aW1lc1t2XSA+IG4pIHJldHVybiAwOwoJCQkJaWYoIWlucVt2XSkgcS5wdXNoKHYpLCBpbnFbdl0gPSAxOwoJCQl9CgkJfQoJfQoJcmV0dXJuIDE7Cn0KCnNpZ25lZCBtYWluKCkgewoJbiA9IHJlYWQoKSwgbSA9IHJlYWQoKTsKCQoJZm9yKGludCBpID0gMTsgaSA8PSBuOyArK2kpIGZhW2ldID0gaTsKCQoJZm9yKGludCBpID0gMTsgaSA8PSBtOyArK2kpIHsKCQl1W2ldID0gcmVhZCgpLCB2W2ldID0gcmVhZCgpOwoJCWFkZEVkZ2UodVtpXSwgdltpXSwgRyksIGFkZEVkZ2UodltpXSwgdVtpXSwgbkcpOwoJCW1lcmdlKHVbaV0sIHZbaV0pOwoJfQoJCgkvKgoJ5bm25p+l6ZuG5Yik5patIDEg5ZKMIG4g5piv5ZCm6IGU6YCa77yI5YW25a6e5rKh5ZWl55SoCgluR1tdIOWtmOWPjei+uSA9PT4gbiAtPiAxCglHW10g5a2Y5q2j5ZCR6L65ID09PiAxIC0+IG4KCSovCgkKCWlmKGZpbmQoMSkgIT0gZmluZChuKSkgewoJCXB1dHMoIi0xIik7CgkJcmV0dXJuIDA7Cgl9CgkKCWRmcygxKTsgbkRmcyhuKTsKCQoJc3RhdGljIGJvb2wgZmxhZ1tNQVhOXSA9IHswfTsKCWZvcihpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSBpZih2aXMxW2ldICYmIHZpc25baV0pIGZsYWdbaV0gPSAxOwoJaWYoIXZpczFbbl0pIHsKCQlwdXRzKCItMSIpOwoJCXJldHVybiAwOwkKCX0KCWZsYWdbMV0gPSBmbGFnW25dID0gMTsKCQoJLyoKCeazqOaEj+i/memHjOaYr+WIpOaWrSAxIOWIsCBuIOS4reavj+S4queCueaYr+WQpuWcqOetlOahiOi3r+W+hOS4iu+8jOaemuS4vueahOaYryAxIH4gbgoJdmlzMVtdIOaYr+S7jiAxIOWIsCBuIOS4iue7j+i/h+eahOeCuQoJdmlzbltdIOaYr+S7jiBuIOWIsCAxIOS4iue7j+i/h+eahOeCuQoJ5Zug5Li65piv5pyJ5ZCR6L6577yM5omA5Lul6KaB5Yik5pat5LiA5LiLIDEg5Y+v5LiN5Y+v5Lul5YiwIG4KCQoJ5q+U5aaCOgoJMyAyCgkzIDEKCTEgMgoJCglhbnM6IC0xCgkqLwoJCglmb3IoaW50IGkgPSAxOyBpIDw9IG07ICsraSkKCQlpZihmbGFnW3VbaV1dICYmIGZsYWdbdltpXV0pIGFkZEVkZ2UodVtpXSwgdltpXSwgOSksIGFkZEVkZ2UodltpXSwgdVtpXSwgLTEpOwoJCglpZighU1BGQSgxKSkgewoJCXB1dHMoIi0xIik7CgkJcmV0dXJuIDA7Cgl9CgkKCS8qCgnlj6rlr7nnrZTmoYjot6/lvoTkuIrnmoTngrnlu7rovrnvvIzot5Hlt67liIbnuqbmnZ8KCeWmguaenOWHuueOsOi0n+eOr++8jOW3ruWIhue6puadn+ezu+e7n+aXoOino+OAggoJKi8KCQoJcHJpbnRmKCIlZCAlZFxuIiwgbiwgbSk7Cglmb3IoaW50IGkgPSAxOyBpIDw9IG07ICsraSkgewoJCXByaW50ZigiJWQgJWQgIiwgdVtpXSwgdltpXSk7CgkJaWYoZmxhZ1t1W2ldXSAmJiBmbGFnW3ZbaV1dKSBwcmludGYoIiVkXG4iLCBkaXNbdltpXV0gLSBkaXNbdVtpXV0pOwoJCWVsc2UgcHV0cygiMSIpOyAvL+maj+S+v+i+k+WHuuWVpe+8jOWPjeato+aXoOeUqOi+ueS4jeW9seWTjQoJfQoJcmV0dXJuIDA7Cn0K