# CFR 507 E. Breaking Good ( Dijkstra )

Problem - E - Codeforces

The first line of input contains two integers n, m (2 ≤ n ≤ 1e5, ), the number of cities and number of roads respectively.
In following m lines there are descriptions of roads. Each description consists of three integers x, y, z (1 ≤ x, y ≤ n, ) meaning that there is a road connecting cities number x and y. If z = 1, this road is working, otherwise it is not.

O( N lg N ) / O( N )

```#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
int upmax( T1 &x, T2 v ){
if( x >= v ) return 0;
x = v; return 1;
}

typedef long long ll;

const int MAXN = ( int ) 1e5;

int N, M;
vector< pair< int, int > > G[ MAXN ];
ll dp[ MAXN ];
int pre[ MAXN ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < M; ++i ){
int u, v, w; cin >> u >> v >> w;
--u, --v;
G[ u ].emplace_back( w, v );
G[ v ].emplace_back( w, u );
}
{
for( int i = 0; i < N; ++i ){
dp[ i ] = - ( 1LL << 50 );
pre[ i ] = -1;
}
priority_queue< pair< ll, int > > pq;
pq.emplace( dp[ 0 ] = 0LL, 0 );
while( not pq.empty() ){
ll d; int u; tie( d, u ) = pq.top(); pq.pop();
if( d != dp[ u ] ) continue;
d *= -1;
for( int i = 0; i < G[ u ].size(); ++i ){
int w, v; tie( w, v ) = G[ u ][ i ];
if( upmax( dp[ v ], - ( d + MAXN + not w ) ) ){
pre[ v ] = u;
pq.emplace( dp[ v ], v );
}
}
}
}
{
set< pair< int, int > > on_path;
for( int u = N - 1; u != 0; u = pre[ u ] ){
int x = u;
int y = pre[ u ];
if( not ( x < y ) ) swap( x, y );
on_path.emplace( x, y );
}
vector< tuple< int, int, int > > ans;
for( int i = 0; i < N; ++i ){
for( int j = 0; j < G[ i ].size(); ++j ){
int a = i, b = G[ i ][ j ].second, c = G[ i ][ j ].first;
if( not ( a < b ) ) continue;
if( on_path.count( make_pair( a, b ) ) ){
if( not c ){
ans.emplace_back( a + 1, b + 1, 1 );
}
} else{
if( c ){
ans.emplace_back( a + 1, b + 1, 0 );
}
}
}
}
cout << ans.size() << endl;
for( int i = 0; i < ans.size(); ++i ){
int a, b, c; tie( a, b, c ) = ans[ i ];
cout << a << " " << b << " " << c << "\n";
}
}
return 0;
}
```