#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int h[N],e[N],ne[N],idx;//数据范围大，稀疏图，邻接表存储
int w[N];
int dist[N];//到源点的距离
bool st[N];
int n,m;
void add(int x,int y,int c)
{
    w[idx]=c;//存x到y边长
    e[idx]=y;ne[idx]=h[x];h[x]=idx++;//邻接表存储
}
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    //利用小根堆，根据距离从小到大排序
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});//{距离，节点号}，顺序不能变，pair排序根据先first在根据second排
    while(heap.size())
    {
        PII k=heap.top();
        heap.pop();
        int ver=k.second,distance=k.first;//取节点号 和 源点距离ver的距离
        if(st[ver]) continue;//如果距离已经确定，则跳过该点（防止重边）
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])//更新ver所连接的节点距离
        {
            int j=e[i];
            if(dist[j]>distance+w[i])//该点到源点距离>ver到源点距离+ver到该点距离
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});//只将被更新的点入堆
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--)
    {
        int x,y,c;
        cin>>x>>y>>c;
        add(x,y,c);
    }
    cout<<dijkstra()<<endl;
    return 0;
}

for (int i = 0; i < k; i ++ )
{
    memcpy(backup, dist, sizeof dist);
    for (int j = 0; j < m ; j ++ )
    {
        int a = edges[j].a, b = edges[j].b, w = edges[j].w;
        dist[b] = min(dist[b], backup[a] + w);//dist[b] = min(dist[b], dist[a] + w);
    }
}

memcpy(backup,dist,sizeof dist);
dist[b]=min(dist[b],backup[a]+w);

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int dist[N],backup[N];
int n,m,k;
struct edge
{
    int a,b,w;
}edge[N];
int bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=1;i<=k;i++)
    {
        memcpy(backup,dist,sizeof dist);
        for(int j=1;j<=m;j++)
        {
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    return dist[n];
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i]={a,b,c};
    }
    int t=bellman_ford();
    if(t>0x3f3f3f3f/2) puts("impossible");
    else cout<<t<<endl;
    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];//防止队列中存重复的点
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        //如果t变小了，那么t所连接的所有节点都有可能变小
        for (int i = h[t]; i != -1; i = ne[i])//检查t所连接的所有节点
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j]) //如果j不在队列中
                {
                    q.push(j);
                    st[j] = true;   //入队并标记
                }
            }
        }
    }
    return dist[n];
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int t = spfa();
    if (t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);
    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int w[N];
int dist[N]
int cnt[N];//记录每个点到起点的边数，当cnt[i] >= n 表示出现了边数>=结点数，必然有环，而且一定是负环！
bool st[N];//判断当前的点是否已经加入到队列当中了；已经加入队列的结点就不需要反复的把该点加入到队列中了
//就算此次还是会更新到起点的距离，那只用更新一下数值而不用加入到队列当中。
//意味着，st数组起着提高效率的作用，不在乎效率的话，去掉也可以
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa()
{
    // memset(dist, 0x3f, sizeof dist);
    // dist[1] = 0;
    // 这里不需要初始化，让dist为0即可，因为有负环dist会不断减小，不断更新
    queue<int> q;//用于检测所有点是否有负环
    for (int i = 1; i <= n; i ++ )
    {
        //判断负环，只从一个点出发，有可能到达不了负环那里，需要一开始就把所有结点放入队列，且标记进入了队列提高效率
        q.push(i);
        st[i] = true;
    }
    while (q.size())//spfa求最短路套路模板
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        //更新与t邻接的边
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];//结点j可以通过中间点t降低距离
                cnt[j] = cnt[t] + 1;//那么结点j在中间点t的基础上加一条到自己的边
                if (cnt[j] >= n) return true;//边数不小于结点数，出现负环，函数结束
                if (!st[j])//若此时j没在队列中，则进队。已经在队列中了，上面已经更新了数值。重复加入队列降低效率
                {
                    q.push(j);//将被改变距离的结点入队
                    st[j] = true;
                }
            }
        }
    }
    return false;//走到这了，函数还没结束，意味着边数一直小于结点数，不存在负环
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    if (spfa()) puts("Yes");
    else puts("No");
    return 0;
}