#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=1e5;
vector<pair<pair<int, int>, int>> graph[maxn];

struct node {
 int idx,dali_ima_sneg,shortest_distance;
 node(){}
 node(int _idx,int _dali_ima_sneg, int _shortest_distance){
    idx = _idx;
    dali_ima_sneg = _dali_ima_sneg;
    shortest_distance = _shortest_distance;
 }
 bool operator < (const node & tmp) const {
   return shortest_distance > tmp.shortest_distance;
 }
};

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0;i<m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        graph[a].push_back(make_pair(make_pair(b,c),d));
        graph[b].push_back(make_pair(make_pair(a,c),d));
    }

    priority_queue<node>pq;
    pq.push(node(1,1,0));
    int shortest = 2e9;
    string res = "";
    bool visited[maxn][2];

    for(int i = 0;i<maxn;i++){
       visited[i][0]=false;
       visited[i][1]=false;
    }

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

        if(visited[c.idx][c.dali_ima_sneg]==true){
            continue;
        }
            visited[c.idx][c.dali_ima_sneg]=true;
        if(c.idx==n){
            if(c.shortest_distance < shortest) {
                shortest = c.shortest_distance;
                if(c.dali_ima_sneg) {
                    res = "DA";
                }
                else {
                    res = "NE";
                }
            }
            else if(c.shortest_distance == shortest) {
                if(c.dali_ima_sneg) {
                    res = "DA";
                }
            }

        }
        for(int i = 0;i< (int)graph[c.idx].size();i++){
            int sosed=graph[c.idx][i].first.first;
            int weight=graph[c.idx][i].first.second;
            int sneg=graph[c.idx][i].second;
            int nov_sneg=min(c.dali_ima_sneg,sneg);
            if(!visited[sosed][nov_sneg]){
                pq.push(node(sosed,nov_sneg,c.shortest_distance+weight));
            }
        }

    }
    cout << shortest << endl << res << endl;
    return 0;
}