Untitled

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1005;
const int INF = 2e9;
int n, m;
struct edge {
    int b, weight, snow;
    edge(int _b, int _weight, int _snow) {
        b = _b;
        weight = _weight;
        snow = _snow;
    }
    
};
vector<edge> graph[maxn];
struct node {
    int idx, cost, snow_only;
    node () {}
    node(int _idx, int _cost, int _snow_only) {
        idx = _idx;
        cost = _cost;
        snow_only = _snow_only;
    }
    bool operator < (const node &tmp) const {
        return cost > tmp.cost;
    }
};
bool visited[maxn][2];
void dijkstra(int S) {
    priority_queue<node> pq;
    pq.push(node(S, 0, 1));
    for(int i = 0; i < maxn; i++) {
        visited[i][0] = false;
        visited[i][1] = false;
    }
    int shortest_path = INF;
    int res_snow = 0;
    while(!pq.empty()) {
        node c = pq.top();
        pq.pop();
        
        if(c.idx == n - 1) {
            if(shortest_path > c.cost) {
                shortest_path = c.cost;
                res_snow = c.snow_only;
            }
            else if(shortest_path == c.cost) {
                res_snow = max(res_snow, c.snow_only);
            }
        }
        
        if(visited[c.idx][c.snow_only]) continue;
        cout << c.idx + 1 << " " << c.cost << " " << c.snow_only << endl;
        visited[c.idx][c.snow_only] = true;
        
        
        for(int i = 0; i < (int) graph[c.idx].size(); i++) {
            int neighbour = graph[c.idx][i].b;
            int weight = graph[c.idx][i].weight;
            int snow = graph[c.idx][i].snow;
//            if(neighbour == 3) {
//                cout << snow << endl;
//            }
            int next_snow = min(snow, c.snow_only);
            if(!visited[neighbour][next_snow]) {
                pq.push(node(neighbour, c.cost + weight, next_snow));
            }
        }
        
    }
    cout << shortest_path << endl;
    if(res_snow) {
        cout << "DA" << endl;
    }
    else {
        cout << "NE" << endl;
    }
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    
    for(int i = 0; i < m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--; b--;
        graph[a].push_back(edge(b, c, d));
        graph[b].push_back(edge(a, c, d));
    }
    dijkstra(0);
    return 0;
}