Dijkstra

#include <bits/stdc++.h>
#define     sf      scanf
#define     pf      printf
#define     inf     INT_MAX
#define     dbg     cout << "Debug" << endl;

using namespace std;

void clr();
void printGrid();

vector < int > adjList[1024];
vector < int > ans;
priority_queue  < int > q;

int par[1234];

int x1,x2,nodes,start,edges,n,a,b,c,last ;
double times;
int visited[1025] ,d[1024];
int cost[1024][1024];

void BFS( int s ){ /// Implementation of Dijsktra Algorithm

    for( int i=0; i<=nodes; i++ ) d[i] = inf;
    q.push( s );
    d[s] = 0;

    while ( !q.empty() ){
        int u = q.top(); q.pop();
        int ucost = d[u];
        int sz = adjList[u].size();

        for( int i=0; i<sz; i++ ){
            int v = adjList[u][i];
            int vcost = ucost + cost[u][v];

            if( vcost < d[v] ){
                d[v] = vcost;
                par[v] = u;
                q.push( v );
            }

        }
    }
}

void solve(){
    x1 = x2 = inf;
    int mx = INT_MIN;
    for( int i=1; i<=nodes; i++ ){
        mx = max( d[i], mx );
    }

    for( int u=2; u<=nodes; u++ ){
        int sz = adjList[u].size();
        for( int j=0; j<sz; j++ ){
            int v = adjList[u][j];
            if( par[u] != v && ((d[v]) < d[u] + cost[v][u]) ){
                cout << u << " " << v << " " << cost[v][u] << endl;
            }
        }
    }
}


int main(){
    #ifndef ONLINE_JUDGE
        freopen("in.txt","rt",stdin);
        freopen("outs.txt","wt",stdout);
    #endif
    clr();
    int kase = 0;

    while( sf ("%d %d",&nodes, &edges) ,nodes + edges ){
        for( int i=1; i<=edges; i++ ){
            sf("%d %d %d",&a, &b, &c);
            adjList[a].push_back( b );
            adjList[b].push_back( a );
            cost[a][b] = cost[b][a] = c;
        }

        BFS(1);
        solve();
        puts("");

        clr();
    }


    return 0;
}

void clr(){
    for( int i=0; i<=nodes; i++ ){
        adjList[i].clear();
        visited[i] = 0;
    }
    memset( cost, 0, sizeof cost );
    for( int i=0; i<=nodes; i++ )d[i] = inf;

}

void printGrid(){
    for( int i=1; i<=nodes; i++ ){
        for( int j=1; j<=nodes; j++ ){
            printf("%d ", cost[i][j] );
        }
        puts("");
    }

}

/*
3 3
1 2 1
1 3 2
2 3 8

3 3
1 2 1
1 3 2
2 3 13

3 3
1 2 5
1 3 10
2 3 5


3 3
1 2 5
2 3 5
1 3 5


12 13
1 3 1
3 8 2
8 9 3
2 10 3
10 11 1
11 12 1
2 4 2
1 2 5
4 5 1
5 12 1
2 6 3
6 7 2
7 5 3

121 156
108 52 58
24 108 89
61 108 11
106 61 73
113 52 67
44 24 22
8 113 12
80 108 39
39 61 70
41 113 41
16 41 5
5 39 66
31 52 85
34 52 37
47 34 80
56 31 44
98 80 84
99 16 39
86 16 70
13 44 48
22 13 32
11 106 77
104 52 41
28 39 74
9 16 68
77 86 29
70 86 50
62 52 5
105 47 46
33 86 76
18 61 13
6 9 86
3 86 25
38 104 60
64 56 89
111 41 52
69 104 64
100 69 30
45 52 17
96 11 31
121 11 82
35 86 32
14 16 19
115 96 54
92 100 78
95 33 26
37 105 31
112 95 40
81 121 82
89 16 2
60 81 17
21 28 12
50 13 6
116 69 98
65 98 82
36 9 88
26 41 6
83 104 70
20 92 13
17 69 16
107 39 93
71 107 42
32 5 75
90 13 52
109 36 99
55 21 77
1 41 43
119 24 20
48 38 70
68 44 50
57 121 28
103 112 58
43 33 32
67 48 6
2 31 57
51 100 16
117 38 100
59 20 34
25 81 16
84 109 98
54 37 90
114 38 15
120 109 80
12 25 14
72 108 39
15 52 80
85 111 31
91 108 74
19 54 42
40 52 58
49 33 18
76 9 59
118 99 83
78 55 22
97 32 91
82 31 36
75 68 97
27 31 83
87 43 54
42 14 41
93 60 63
29 27 2
53 72 20
66 72 53
79 69 51
46 93 35
30 99 68
73 60 80
58 64 2
94 42 25
110 61 50
88 94 34
4 40 94
74 119 13
63 108 56
10 66 12
7 29 41
102 21 73
23 64 87
101 67 37
62 91 46
49 13 74
34 86 86
118 24 72
111 120 26
57 28 5
27 91 81
120 76 78
121 100 29
15 19 10
79 13 70
113 33 79
17 18 53
102 10 75
77 118 83
4 39 60
3 99 22
99 73 75
54 50 71
17 121 68
9 86 80
111 9 33
77 84 29
101 52 8
96 13 29
116 13 56
49 51 77
113 32 67
70 119 98
102 11 39
11 64 31
83 40 26
34 69 19
32 8 17
113 59 1
105 81 28
*/