507E
Breaking Good
dfs and similar, graphs, shortest
paths
x328
<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+zOLS4qO6uPjE49K70Km1wMK3o6y1wMK3s6S2yLa8zqoxo6y1wMK309DBvbj217TMrL/J08O6zbK7v8nTw6GjINGw1dLSu8z1MbW9TrXE1+62zMK3o6zKubXDuMPX7rbMwrfJz7XEtcDCt8irsr+/ydPDo6zG5Mv7tcDCt8irsr+yu7/J08OjrNKqx/O4xLHk17TMrLXEtcDCt8r9wb++ocG/0KGhozwvcD4KPHA+PGJyPgo8L3A+CjxwPrfWzvajujEtTrXE1+62zMK3tcSzpLbI0ru2qMrHyLe2qLXEo6zJ6M6q1+62zMK3s6S2yESjrMno1+62zMK3yc+/ydPDtcS1wMK3yv3Bv86qWKOsy/nT0LXAwrfW0L/J08O1xMr9wb/OqlmhoyDEx8O00OjSqrjEseS1xMr9wb++zcrHRC1YJiM0MztZLVggPUQmIzQzO1ktMlihozwvcD4KPHA+RNPrWba8zqqzo8G/o6zL+dLUztLDx9Kqyrm1w1i+ocG/tPOho7bU09rEs7Hfyse38b/JxNzU2tfutszCt8nPztLDx7/J0tTTw2Rpc1t1XSYjNDM7MT09ZGlzW3Zd0enWpKGjyLu687bU09rU2tfutszCt8nPtcSx36OsztLDx7/J0tRkcMfzWLXE1+608yYjMjA1NDA7oaM8L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;">#include
using namespace std;
typedef long long LL;
const int INF = 0x7fffffff;
const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
struct edge {
int v, c;
edge() {}
edge(int v, int c): v(v), c(c) {}
};
map, int> M;
vector G[N];
queue Q;
int n, m, x[N], y[N], c[N];
int dis[N], dp[N], pre[N];
int ax[N], ay[N], ac[N];
bool vis[N];
int main() {
#ifdef Tally_Ho
freopen("in.txt", "r", stdin);
#endif // Tally_Ho
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &x[i], &y[i], &c[i]);
G[x[i]].push_back(edge(y[i], c[i]));
G[y[i]].push_back(edge(x[i], c[i]));
}
Q.push(1);
while(!Q.empty()) {
int u = Q.front();
Q.pop();
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i].v;
int c = G[u][i].c; //1:working
if(!vis[v]) {
dis[v] = dis[u] + 1;
vis[v] = 1;
Q.push(v);
}
if(dis[v] == dis[u] + 1 && dp[u] + c >= dp[v]) {
pre[v] = u;
dp[v] = dp[u] + c;
}
}
}
int v = n;
while(v != 1) {
M[make_pair(v, pre[v])] = 1;
v = pre[v];
}
int len = 0;
for(int i = 0; i < m; i++) {
bool onRoad = M[make_pair(x[i], y[i])] || M[make_pair(y[i], x[i])];
if(onRoad && c[i] == 0) {
ax[len] = x[i], ay[len] = y[i], ac[len++] = 1;
} else if(!onRoad && c[i] == 1) {
ax[len] = x[i], ay[len] = y[i], ac[len++] = 0;
}
}
printf("%d\n", len);
for(int i = 0; i < len; i++)
printf("%d %d %d\n", ax[i], ay[i], ac[i]);
return 0；
}
