Contest 2 — Problem C: The Coupon

**Bài toán.** A weighted undirected graph has n vertices and m edges. You may halve the weight of exactly one edge along your trip (floor division; the coupon applies to at most one edge use over the whole trip). Minimize the total weight of a path from vertex 1 to vertex n. **Constraints:** 2 ≤ n ≤ 100000; 1 ≤ m ≤ 200000; 1 ≤ w ≤ 10^9. **Input:** line 1: n, m; then m lines: u, v, w. **Output:** one integer — the minimum total.