#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> using namespace std; int n,m; const int maxn=505; struct Node { int x;int val; }node[maxn]; struct cmp { bool operator ()(const Node &a,const Node &b) { return a.val<b.val; } }; const int INF=10000000; int dis[maxn]; int vis[maxn]; int Map[maxn][maxn]; void djs(int x) { for(int i=1;i<=n;i++){ dis[i]=INF;vis[i]=0; } dis[x]=0;vis[x]=1; Node k; k.x=x;k.val=0; priority_queue<Node,vector<Node> ,cmp> q; q.push(k); while(!q.empty()){ Node k=q.top();q.pop(); int cur=k.x;vis[x]=1; for(int i=1;i<=n;i++){ if(dis[i]>dis[cur]+Map[cur][i]){ dis[i]=dis[cur]+Map[cur][i]; if(!vis[i]){ Node k; k.x=i;k.val=dis[i]; q.push(k); } } } } } int main() { int ret=0; while(cin>>n>>m,++ret&&n||m){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) Map[i][j]=INF; for(int i=0;i<m;i++){ int a,b,c;cin>>a>>b>>c; if(Map[a][b]>c) Map[a][b]=Map[b][a]=c; } djs(1); double ans=0;int sign=1; for(int i=1;i<=n;i++) if(dis[i]>ans){ ans=dis[i];sign=i; } double ans1=0;int a;int b; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++)if(Map[i][j]!=INF) { double t=(dis[i]+dis[j]+Map[i][j])/2.0; if(t>ans1) { ans1=t; a=i;b=j; } } } // for(int i=1;i<=n;i++) // cout<<dis[i]<<endl; if(ret!=1) cout<<endl; printf("System #%d ",ret); if(ans1>ans){ printf("The last domino falls after %.1f seconds, between key dominoes %d and %d. ",ans1,a,b); } else{ printf("The last domino falls after %.1f seconds, at key domino %d. ",ans,sign); } } return 0; }