Hello, I'm trying to solve the problem Tax;

In a first glance, it looks like a little modified Dijksta algorithm, using the weight as the max value of the last weight edge weight and the current weight, like the code I did here.

But unfortunately this idea only work for 3 test cases, can you point what is wrong with this code, or the right idea for tackle this problem ?

Thanks in advance.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <memory>
#include <iomanip>
#include <numeric>
#include <functional>
#include <new>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <climits>
#include <cctype>
#include <ctime>

#define REP(i, n) for(int (i) = 0; i < n; i++)
#define FOR(i, a, n) for(int (i) = a; i < n; i++)
#define FORR(i, a, n) for(int (i) = a; i <= n; i++)
#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
#define sz(n) n.size()
#define pb(n) push_back(n)
#define all(n) n.begin(), n.end()

template<typename T> T gcd(T a, T b) {
    if(!b) return a;
    return gcd(b, a % b);
}
template<typename T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

using namespace std;

typedef long long ll;
typedef long double ld;

const ll INF = 1000010100980980LL;
const int MAXN = 100009;
int N, M, a, b, c;
vector<pair<int, int> > graph[MAXN];
ll dist[MAXN];

ll func(int hashiri, int saigo) {
    for(int i = 0; i <= N; i++) dist[i] = INF;

    dist[hashiri] = 0LL;
    priority_queue<pair<int, int> > q;

    //Last bigger, index;
    q.push(make_pair(0, hashiri));

    while(!q.empty()) {
        int last = q.top().first, index = q.top().second; q.pop();

        for(int i = 0; i < graph[index].size(); i++) {
            int next = graph[index][i].first, cost = graph[index][i].second;
            int real_cost = max(cost, last);

            if(next == saigo) real_cost += cost;

            if(dist[index] + real_cost < dist[next]) {
                dist[next] = dist[index] + real_cost;
                q.push(make_pair(cost, next));
                printf("%d %d\n", index, next);
            }
        }
    }

    return dist[saigo];
}

int main(void) {
    scanf("%d%d", &N, &M);

    REP(i, M) {
        scanf("%d%d%d", &a, &b, &c);
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }

    printf("%lld\n", func(1, N));

    return 0;
}