//2024.4.9
//https://www.acwing.com/problem/content/853/
//851.spfa求最短路
/*
思路:边权可能为负数,但一定不存在负权回路
spfa算法就是对bellman_ford算法做优化。因为只有边<a,b>结点的a结点发生了变化,才会使得b结点的最短距离发生变化
所以我们对此进行优化,把发生变化的a点存入队列中。
也就是说,只有我更新过谁,我才拿这个点对其他点进行更新
*/
#pragma GCC target ("avx")
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
using namespace __gnu_cxx;
using ll = long long;
typedef pair<int, int> PII;
const int N = 150010;
int n,m;//n个点,m条边
int h[N], e[N], ne[N], w[N], idx;//邻接表的存储方式
int d[N];//存最短路径
bool st[N];//st[i]判断队列中是否已经存在下标为i的点
void add(int a,int b,int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int spfa(){
memset(d,INF, sizeof d);
d[1]=0;
queue<int> p;
p.push(1);
st[1] = true;
while (p.size())
{
auto t = p.front();
p.pop();
st[t] = false;
for(int i=h[t]; i!=-1; i=ne[i]){
int j = e[i];
if(d[j] > d[t] + w[i]){
d[j] = d[t] + w[i];
if(!st[j]){
st[j] = true;
p.push(j);
}
}
}
}
return d[n];
}
signed main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
memset(h,-1,sizeof h);//初始化头节点为-1
cin>>n>>m;
while (m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t = spfa();
if(t == INF) cout<<"impossible"<<endl;
else cout<<t<<endl;
return 0;
}