参加科学大会

#include <bits/stdc++.h>
using namespace std;

//使用队列进行bfs
void find(vector<vector<int>> &dist, vector<bool> &visited, int index,
          int target) {
  std::queue<int> q;
  q.push(index);
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int i = 0; i < visited.size(); i++) {
      if (i == cur || dist[cur][i] == INT32_MAX)
        continue;
      if(cur!=index)
      //更新原路径到当前节点最小值
      dist[index][i] = min(dist[index][i], dist[index][cur] + dist[cur][i]);
      if (!visited[i] && i != target)
        q.push(i);
    }
    //遍历完cur的邻接点，把cur置为已访问
    visited[cur] = true;
  }
}
int main() {
  int M, N;
  cin >> N >> M;
  std::vector<vector<int>> dist(N, vector<int>(N, INT32_MAX));
  for (int i = 0; i < M; i++) {
    int s, d, w;
    cin >> s >> d >> w;
    dist[s - 1][d - 1] = w;
  }
  vector<bool> visited(N, false);
  find(dist, visited, 0, N - 1);
  //如果没找到则返回-1
  auto ans = dist[0][N - 1] == INT32_MAX ? -1 : dist[0][N - 1];
  cout << ans;
  return 0;
}

/**
 * 思路：单源最短路径问题，可以使用 Dijkstra 算法来解决。
 * 
 * 初始化路线矩阵 road，用于存储各站点之间的距离。初始时，将所有距离设为无穷大。
 * 
 * 初始化距离数组 dist，用于存储从起点到各站点的最短距离。
 * 初始时，将起点到各站点的距离设为无穷大，起点到起点的距离设为 cost1（起点站的交流时间）。
 * 
 * 初始化站点访问数组 isVisited，初始时，所有站点都未访问。
 * 
 * 选择起点 s 并将其标记为已访问。
 * 
 * 迭代以下步骤，直到所有站点都被访问：
 *     在未访问的站点中，选择距离最小的站点 v。
 *     将站点 v 标记为已访问。
 *     更新未访问站点的距离：对于每个未访问站点 j，如果从 v 到 j 的距离小于 dist[j]，则更新 dist[j]。
 * 
 * 返回 dist[n] + cost1，即到达终点的最短距离加上起点站的交流时间。
*/

import java.util.Scanner;

public class Main {
    public static void init(int[][] road, int n) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                road[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    public static int dijkstra(int[][] road, int s, int n, int cost1) {
        int[] dist = new int[n + 1]; // 存储从起点 s 到各个站点的距离
        boolean[] isVisited = new boolean[n + 1]; // 记录站点是否被访问过

        for (int i = 2; i <= n; i++) {
            dist[i] = road[s][i]; // 初始化距离数组，将起点到各站点的距离设为初始值
        }

        dist[s] = cost1; // 起点的距离设为 cost1
        isVisited[s] = true; // 起点标记为已访问

        for (int i = 2; i < n; i++) {
            int minDist = Integer.MAX_VALUE; // 初始化最小距离为无穷大
            int v = 1;

            for (int j = 1; j <= n; j++) {
                if (!isVisited[j] && dist[j] < minDist) { // 找到未访问的站点中距离最小的站点
                    minDist = dist[j];
                    v = j;
                }
            }

            isVisited[v] = true; // 将找到的站点标记为已访问

            for (int j = 1; j <= n; j++) {
                if (!isVisited[j] && road[v][j] < Integer.MAX_VALUE) { // 更新未访问站点的距离
                    int temp = dist[v] + road[v][j];
                    dist[j] = Math.min(dist[j], temp);
                }
            }
        }
        return dist[n] + cost1; // 返回最终的距离，即到达终点的最短距离加上 cost1
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt(); // 总站点数
        int M = in.nextInt(); // 总公路数
        int[][] road = new int[N + 1][N + 1]; // 路线矩阵，表示站点之间的距离
        init(road, N); // 初始化路线矩阵

        // 输入数据
        for (int i = 0; i < M; i++) {
            int S = in.nextInt();
            int E = in.nextInt();
            int V = in.nextInt();
            road[S][E] = V;
        }
        System.out.println(dijkstra(road, 1, N, 0));
    }
}