Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

data class Edge(val u: Int, val v: Int, val w: Int)

fun main(args: Array<String>) {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))
    
    // Читаем число вершин и рёбер
    val firstLine = reader.readLine().split(" ")
    val n = firstLine[0].toInt()
    val m = firstLine[1].toInt()
    
    // Считываем рёбра (приводим номера вершин к 0‑индексации)
    val edges = Array(m) {
        val parts = reader.readLine().split(" ")
        val u = parts[0].toInt() - 1
        val v = parts[1].toInt() - 1
        val w = parts[2].toInt()
        Edge(u, v, w)
    }
    
    // Сортируем рёбра по возрастанию веса
    edges.sortBy { it.w }
    
    // DSU с поддержкой двудольности.
    // parent[i] – родитель вершины i, color[i] – цвет вершины i относительно представителя.
    val parent = IntArray(n) { it }
    val rank = IntArray(n) { 0 }
    val color = IntArray(n) { 0 } // 0 или 1; изначально все 0
    
    // Функция find с компрессией пути; обновляет color[x] – отношение цвета к корню.
    fun find(x: Int): Int {
        if (parent[x] != x) {
            val root = find(parent[x])
            color[x] = color[x] xor color[parent[x]]
            parent[x] = root
        }
        return parent[x]
    }
    
    // Осуществляет объединение вершин x и y с требуемой разницей diff (для нас всегда diff=1, т.е. вершины должны оказаться в разных группах).
    // Если x и y уже в одной компоненте, то проверяется, что их цвета отличаются; если нет – обнаружен конфликт.
    fun union(x: Int, y: Int, diff: Int): Boolean {
        val rx = find(x)
        val ry = find(y)
        if (rx == ry) {
            return (color[x] xor color[y]) == diff
        }
        // Объединяем по рангу: меньшую компоненту присоединяем к большей.
        if (rank[rx] < rank[ry]) {
            parent[rx] = ry
            // Обновляем цвет для представителя присоединяемой компоненты:
            // Хотим добиться: color[x] xor (новый цвет связи) xor color[y] == diff.
            color[rx] = color[x] xor color[y] xor diff
        } else {
            parent[ry] = rx
            color[ry] = color[x] xor color[y] xor diff
            if (rank[rx] == rank[ry]) {
                rank[rx]++
            }
        }
        return true
    }
    
    // Обрабатываем рёбра по возрастанию веса.
    // Первое ребро, при добавлении которого обнаруживается конфликт, и есть искомое (его вес — максимальное, при котором минимальное внутреннее ребро максимально).
    var answer = 0
    for (edge in edges) {
        // Для ребра с весом edge.w требуем, чтобы его концы оказались в разных группах.
        if (!union(edge.u, edge.v, 1)) {
            answer = edge.w
            break
        }
    }
    
    writer.write(answer.toString())
    writer.newLine()
    writer.flush()
    reader.close()
    writer.close()
}