vijos-1046.cpp

/*
    Luna Capsule / vijos-1046
    
    Problem: https://vijos.org/p/1046
    Record: https://vijos.org/records/53e9a3f748c5fc6f3c8b457f
*/

#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

unsigned min(unsigned a, unsigned b) {
    return (a > b) ? b : a;
}

unsigned process(unsigned n, unsigned m) {
    unsigned f[101][101], g[101][101];
    unsigned i, j, k, a, b, len, ans = 1024000;
    
    /* Initialize with Maximum */
    for(i = 1; i <= n; i++)
        for(j = 1;j <= n; j++)
            f[i][j] = g[i][j] = 1024000;
    
    /* Read input */
    for(i = 1; i <= m; i++) {
        cin >> a >> b >> len;
        f[a][b] = f[b][a] = g[a][b] = g[b][a] = len;
    }
    
    /* Floyd with minimal loop */
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
                ans = min(f[i][j] + g[i][k] + g[k][j], ans);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j] = min(f[i][k] + f[k][j], f[i][j]);
    }
    
    if (ans == 1024000)
        cout << "No solution." << endl;
    else
        cout << ans << endl;
}

int main() {
    unsigned n, m;
    while (scanf("%d %d", &n, &m) != EOF)
        process(n, m);
}