What's wrong with my implementation of bellman-ford?

i am clueless as to what is wrong with this piece of code. its not working as expected. its expected to display the shortest path from vertex 1 to N. but its failing on a lot of cases. one such case is 3 1 1 2 1 it shows the answer as 1 25 -1 3 which is wrong... any help would be appreciated. Thanks.

#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
using namespace std;

struct Edge{
    int I, W;
};

vector <int> dist;
vector <int> parent;
bool bellman_ford(const vector< vector <Edge> > &graph, int n){
    dist[1] = 0;
    parent[1] = 0;
    for(int k = 1; k <= n-1; k++){
        for(int i = 1; i <= n; i++){
            int len = graph[i].size();
            for(int j = 0; j < len; j++){
                int v = graph[i][j].I;
                int w = graph[i][j].W;
                if(dist[v] > dist[i] + w){
                    dist[v] = dist[i] + w;
                    parent[v] = i;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        int len = graph[i].size();
        for(int j = 0; j < len; j++){
            int v = graph[i][j].I;
            int w = graph[i][j].W;
            if(dist[v] > dist[i] + w){
                return false;
            }
        }
    }
    return true;
}

int main(void){
    int n, m, x, y, w;
    scanf("%d%d", &n, &m);
    dist.resize(n+1, 10000000);
    parent.resize(n+1, -1);
    vector < vector <Edge> > graph (n+1, vector <Edge> (0)) ;
    for(int i = 0; i < m; i++){
        scanf("%d%d%d", &x, &y, &w);
        Edge a, b;
        a.I = y;
        b.I = x;
        a.W = b.W = w;
        graph[x].push_back(a);
        graph[y].push_back(b);
    }
    if(bellman_ford(graph, n)){
        int k = n;
        vector<int>ans;
        ans.push_back(n);
        while(parent[k] != 0){
            ans.push_back(parent[k]);
            k = parent[k];
        }
        for(int i = ans.size()-1; i >= 0; i--){
            printf("%d ", ans[i]);
        }
        printf("\n");
    }
}