#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
using namespace  std;
struct node {
    int index,shortest_path,snow;

    node(int i,int p,int s){
        index = i;
        shortest_path = p;
        snow = s;
    }

    bool operator < (const node &tmp)const{
        return shortest_path > tmp.shortest_path;
    }
};
struct broevi {
    int b,c,d;

    broevi(int _b,int _c, int _d){
        b = _b;
        c = _c;
        d = _d;
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    vector<broevi> graph [n + 5];
    for (int i = 0; i < m; i++) {
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        graph[a].push_back(broevi(b,c,d));
        graph[b].push_back(broevi(a,c,d));
    }
   priority_queue<node> pq;
   pq.push(node(1,0,1));

   vector<bool> visited (n+1, false);
   vector<int> distance ( n+1,2e9);

   while (!pq.empty()){
       node current = pq.top();
       pq.pop();

       visited[current.index] = true;
       if(current.index == n && current.snow == 1){
           cout << current.shortest_path << endl;
           cout << "DA" << endl;
           break;
       }
       if(current.index == n && current.snow == 0){
           cout << current.shortest_path << endl;
           cout << "NE" << endl;
           break;
       }
       for (int i = 0; i <graph[current.index].size(); i++) {
           int sosed = graph[current.index][i].b;
           int pat = graph[current.index][i].c;
           int sneg = graph[current.index][i].d;

           if(!visited[sosed] && sneg * current.snow == 1 and current.shortest_path + pat < distance[sosed]) {
               pq.push(node(sosed,current.shortest_path+pat,current.snow));
               distance[sosed] = current.shortest_path + pat;
           }
           else if (!visited[sosed] ){
               pq.push(node(sosed,current.shortest_path+pat,0));
           }
       }
   }
    return 0;
}