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 nodes,start,edges,n,a,b,c ;
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;
                q.push( v );
            }
        }

    }

}


int main(){
    #ifndef ONLINE_JUDGE
        freopen("in.txt","rt",stdin);
        freopen("out.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);
        int last = nodes,counter = 0 ;
        // for( int i=1; i<=nodes; i++ ) cout << d[i] << endl;


        if( d[nodes-1] == d[nodes] ){
            printf("System #%d\nThe last domino falls after %.1lf seconds, between key dominoes %d and %d.\n\n", ++kase, (( cost[nodes][nodes-1] * 1.00 ) / 2.00) + d[nodes] , nodes-1, nodes );
        }
        else if( d[nodes-1] != d[nodes] ){
            printf("System #%d\nThe last domino falls after %.1lf seconds, at key domino %d.\n\n", ++kase, d[nodes]*1.00, nodes );
        }

        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("");
    }

}