1WA3enwz

1//
2//  main.cpp
3//  Domino Effect
4//
5//  Created by Panagiotis Hadjicostas on 13/12/2019.
6//  Copyright © 2019 Panagiotis Hadjicostas. All rights reserved.
7//
8#include <iostream>
9#include <vector>
10#include <queue>
11typedef long long ll;
12using namespace std;
13typedef pair<ll,ll> pp;
14typedef vector<ll> vi;
15typedef vector<pp> vii;
16vector<vii> A;
17priority_queue< pp, vector<pp>, greater<pp> > pq;
18vi dist;
19
20void dijkstra(ll s){
21    dist[s] = 0;
22    pq.push(pp(0, s));
23    
24    while (!pq.empty()) {
25        
26        ll w = pq.top().first;
27        ll u = pq.top().second;
28        pq.pop();
29        if (w > dist[u]){
30            continue;
31        }
32        for (int j = 0; j < A[u].size(); j++) {
33            pp v = A[u][j];
34            if (dist[u] + v.second < dist[v.first]) {
35                dist[v.first] = dist[u] + v.second;
36                pq.push(pp(dist[v.first], v.first));
37            }
38        }
39    }
40}
41
42
43int main() {
44    ll x,y,z;
45    ll n,m;
46    ll poss=0;
47    while(cin>>n>>m&&n!=0){
48        poss++;
49        A.assign(n+1, vii());
50        dist.assign(n+1, 2000000000);
51        for(ll i=0; i<m;i++){
52            cin>>x>>y>>z;
53            A[x].push_back(pp(y,z));
54            A[y].push_back(pp(x,z));
55        }
56        dijkstra(1);
57        float maxx=0.0;
58        float temp=0;
59        ll ap=1,se=0;
60        for(ll i=1;i<=n;i++){
61            if(dist[i]!=2000000000){
62                if(dist[i]>maxx){
63                    maxx=dist[i];
64                    ap=i;
65                    
66                }
67            }
68        }
69        
70        //cout<<endl<<maxx<<endl;
71            
72        
73        for(ll i=1;i<=n;i++){
74            for(ll j=0;j<A[i].size();j++){
75                if(dist[A[i][j].first]!=2000000000&&dist[i]!=2000000000){
76                    ll a=max(dist[A[i][j].first],dist[i]);
77                    ll b=min(dist[A[i][j].first],dist[i]);
78                    ll c=A[i][j].second;
79                    temp=a+(c-a+b)/2.0;
80                    
81                    if(maxx<temp){
82                        maxx=temp;
83                        ap=i;
84                        se=A[i][j].first;
85                    }
86                }
87                else if(dist[A[i][j].first]==2000000000&&dist[i]==2000000000){
88                    
89                }
90                else{
91                    ll a=min(dist[A[i][j].first],dist[i]);
92                    ll b=0;
93                    
94                    ll c=A[i][j].second;
95                    float temp=a+(c-a+b)/2;
96                    
97                    if(maxx<temp){
98                        maxx=temp;
99                        ap=i;
100                        se=A[i][j].first;
101                    }
102                }
103                
104            }
105        }
106        
107        //cout<<maxx<<endl;
108        cout<<"System #" <<poss<<endl;
109        cout<<"The last domino falls after ";
110        printf("%.1f", maxx);
111        if (se==0){
112            cout << " seconds, at key domino "<<ap<<"."<<endl;
113        }
114        else
115            cout<<" seconds, between key dominoes "<<ap<<" and "<<se<<"."<<endl;
116        cout<<endl;
117        //The last domino falls after 8.0 seconds, between key dominoes 2 and 4.
118
119        //cout<<ap<<" "<<se<<" "<<double(maxx)<<endl;
120    }
121    return 0;
122}