```#include <bits/stdc++.h>
#define N 1005
#define LL long long
using namespace std;
LL n, m, i, j, k, a, b, c, v, s, mp[N][N], h[N];
struct AB{
LL a, b, c, n;
} d[N*20];
struct AS{
LL a, s, v;
bool operator < (const AS &A) const{
if(s != A.s) return s > A.s;
return v > A.v;
}
} t;
priority_queue <AS> q;
int main(){
scanf("%lld%lld", &n, &m);
for(i=1; i<=m; i++){
scanf("%lld%lld%lld", &a, &b, &c);
d[i].a = a, d[i].b = b, d[i].c = c;
d[i].n = h[a], h[a] = i;
}
memset(mp, 9, sizeof(mp));
q.push((AS){1, mp[1][1]=0, 1});
while(q.size()){
t = q.top(), q.pop();
a = t.a, s = t.s, v = t.v;
if(a == n) break;
if(v > n || s>mp[a][v]) continue;
for(i=h[a]; i; i=d[i].n){
b = d[i].b, c = d[i].c;
if(s+v*c < mp[b][v+1]){
mp[b][v+1] = s + v*c;
q.push((AS){b, mp[b][v+1], v+1});
}
}
}
printf("%lld\n", s);
return 0;
}```
```#include <bits/stdc++.h>
#define N 1005
#define LL long long
using namespace std;
LL mp[N][N], v, s, ans=1e18;
LL n, m, i, j, k, a, b, c, h[N];
struct AB{
LL a, b, c, n;
} d[N*20], q[N*400];
int main(){
scanf("%lld%lld", &n, &m);
for(i=1; i<=m; i++){
scanf("%lld%lld%lld", &a, &b, &c);
d[i].a = a, d[i].b = b, d[i].c = c;
d[i].n = h[a], h[a] = i;
}
memset(mp, 9, sizeof(mp));
q[1] = (AB){1, 1, mp[1][1]=0};
for(i=j=1; i<=j; i++){
a = q[i].a, s = q[i].c, v = q[i].b;
if(j > n*400) break;
for(k=h[a]; k; k=d[k].n){
b = d[k].b, c = d[k].c;
if(v<n && s+v*c < mp[b][v+1]){
mp[b][v+1] = s + v*c;
q[++j] = (AB){b, v+1, mp[b][v+1]};
}
}
}
for(i=1; i<=n; i++) ans = min(ans, mp[n][i]);
printf("%lld\n", ans);
return 0;
}```

```#include <bits/stdc++.h>
#define N 1005
#define LL long long
using namespace std;
LL mp[N][N], v, s, ans=1e18;
LL n, m, i, j, k, a, b, c, h[N];
struct AB{
LL a, b, c, n;
} d[N*20];
void dfs(LL a, LL s, LL v){
int b, c, i;
if(a == n){
ans = min(ans, s);
return;
}
if(s >= mp[a][v]) return;
mp[a][v] = s;
for(i=1; i<v; i++){
if(mp[a][i] < s) return;
}
for(i=h[a]; i; i=d[i].n){
b = d[i].b, c = d[i].c;
dfs(b, s+c*v, v+1);
}
}
int main(){
scanf("%lld%lld", &n, &m);
for(i=1; i<=m; i++){
scanf("%lld%lld%lld", &a, &b, &c);
d[i].a = a, d[i].b = b, d[i].c = c;
d[i].n = h[a], h[a] = i;
}
memset(mp, 9, sizeof(mp));
dfs(1, 0, 1);
printf("%lld\n", ans);
return 0;
}```