spfa

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, dis[N], h[N], idx;
bool vis[N];
struct edge
{
    int n, t, l;
    edge(){}
    edge(int tt, int ll, int nn)
    {
        n = nn, t = tt, l = ll;
    }
}e[N];
void addEdge(int ff, int tt, int ll)
{
    e[idx] = edge(tt, ll, h[ff]);
    h[ff] = idx ++ ;
}
int spfa()
{
    memset(dis, 0x3f, sizeof dis);
    queue<int> q;
    dis[1] = 0;
    q.push(1);
    vis[1] = true;
    while(!q.empty())
    {
        int f = q.front();
        q.pop();
        vis[f] = false;
        for(int i = h[f]; ~i; i = e[i].n)
        {
            int t = e[i].t, l = e[i].l;
            if(dis[t] > dis[f] + l)
            {
                dis[t] = dis[f] + l;
                if(!vis[t]) 
                {
                    q.push(t);
                    vis[t] = true;
                }
            }
        }
    }
    if(dis[n] > INF / 2) return INF;
    return dis[n];
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 0; i < m; i ++ )
    {
        int f, t, l;
        cin >> f >> t >> l;
        addEdge(f, t, l);
    }

    int temp = spfa();
    if(temp == INF) puts("impossible");
    else cout << temp << endl;


    return 0;
}