void try_hard() {
    int w = n;
    for (int u = 1 ; u <= n; u = u + 1 ) {
        for (int v = 1 ; v <= n; v = v + 1 ) {
            g[u][v] = min ( g[u][v], g[u][w] + g[w][v] ) ;
        }
    }


    for (int w = 1 ; w <= n; w = w + 1 ) {
        int u = n;
        for (int v = 1 ; v <= n; v = v + 1 ) {
            g[u][v] = min ( g[u][v], g[u][w] + g[w][v] ) ;
        }
    }

    for (int w = 1 ; w <= n; w = w + 1 ) {
        for (int u = 1 ; u <= n; u = u + 1 ) {
            int v = n;
            g[u][v] = min ( g[u][v], g[u][w] + g[w][v] ) ;
        }
    }
}