I am trying to solve the following task:

Given a directed weighted graph with edges whose weight can be negative. Find the length of the longest path from the first to the last vertex. If such a path does not exist, output “:(“. If such a path is infinitely long, output “:)”.

My code works correctly for 21 test cases out of 22. The problem is that I can’t pick the tests for which the code is not working correctly. Here is my code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Node
{
    int val = 0;
    bool isNull = true;
};

struct Edge
{
    int from;
    int to;
    int cost;
};

int main()
{
    int n, m;
    cin >> n >> m;

    vector<Node> nodes(n);
    vector<Edge> edges(m);

    for (int i = 0; i < m; i++)
    {
        int from, to, cost;
        cin >> from >> to >> cost;
        edges[i] = { from - 1, to - 1, cost };
    }
    nodes[0].val = 0;
    nodes[0].isNull = false;

    for (int i = 0; i < max(nodes.size() - 1, (vector<Node>::size_type)1); i++)
    {
        for (auto [from, to, cost] : edges)
        {
            if (!nodes[from].isNull && (nodes[to].isNull || nodes[to].val < nodes[from].val + cost))
            {
                nodes[to].isNull = false;
                nodes[to].val = nodes[from].val + cost;
            }
        }
    }

    if (nodes.back().isNull)
    {
        cout << ":(";
        return 0;
    }

    for (auto [from, to, cost] : edges)
    {
        if (!nodes[from].isNull && nodes[to].val < nodes[from].val + cost)
        {
            for (int i = 0; i < max(nodes.size() - 1, (vector<Node>::size_type)1); i++)
            {
                for (auto [from, to, cost] : edges)
                {
                    if (!nodes[from].isNull && nodes[to].val < nodes[from].val + cost)
                    {
                        if (to == nodes.size() - 1)
                        {
                            cout << ":)";
                            return 0;
                        }

                        nodes[to].val = nodes[from].val + cost;
                    }
                }
            }
        }
    }

    cout << nodes.back().val;

    return 0;
}

Also I know, that the correct answer for the test that the program failed is “:)”, because I tried to send a program, which outputs “:)” in all cases, and it passed this test (but, obviously, did not passed lots of other). That means that the problem is probably in the part of program, which checks when to output “:)”.

So the question is: what is wrong in my code?