include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

define endl ‘\n’

using namespace std;

const int N = 510;

int n, m;
int dist[N];
int g[N][N];
bool st[N];

int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n-1; i)//一共有n个点所以遍历n-1次即可得到第一个点到第n个点的最小距离
{
int t = -1;//每次大循环开头让t=-1便于找到剩余点中第一个没有被当作起点的点
for (int j = 1; j <= n; j)//找到距离上一个被当作起点的距离最近的点
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

        for (int j = 1; j <= n; j++)//用新的起点更新所有点到1的距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);//如果有间断，则间断之后的点的dist值全是0x3f3f3f3f
        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f)return -1;
    return dist[n];

}

int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a, b, c;
memset(g, 0x3f, sizeof g);//让g无穷大便于g[a][b] = min(g[a][b], c)的操作
cin >> n >> m;
while (m–)
{
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);

}
cout << dijkstra() << endl;

return 0;

}