package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

func Run(_r io.Reader, _w io.Writer) {
	in := bufio.NewReader(_r)
	out := bufio.NewWriter(_w)
	defer out.Flush()

	const INF = int(0x1f1f1f1f)
	var n, m, u, v, w int
	fmt.Fscan(in, &n, &m)

	dis := make([][]int, 128)
	mp := make([][]int, 128)
	for i := 0; i < len(dis); i++ {
		dis[i] = make([]int, 128)
		mp[i] = make([]int, 128)
	}

	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			if i != j {
				dis[i][j], mp[i][j] = INF, INF
			}
		}
	}

	for i := 0; i < m; i++ {
		fmt.Fscan(in, &u, &v, &w)
		dis[u][v] = w
		dis[v][u] = w
		mp[u][v] = w
		mp[v][u] = w
	}

	hasSolution := false
	ans := INF

	for k := 1; k <= n; k++ {
		for i := 1; i < k; i++ {
			for j := i + 1; j < k; j++ {
				ans = min(ans, dis[i][j]+mp[i][k]+mp[k][j])
				hasSolution = true
			}
		}
		for i := 1; i <= n; i++ {
			for j := 1; j <= n; j++ {
				dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
				dis[j][i] = dis[i][j]
			}
		}
	}
	if !hasSolution {
		fmt.Fprintln(out, "No solution.")
	} else {
		fmt.Fprintln(out, ans)
	}
}

func main() {
	Run(os.Stdin, os.Stdout)
}

怎会如此，用python写的一样的就能AC......