#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
typedef pair<int,int> ip;
using namespace std;
class graph{
    int g[100][100];
    int node_count,edge_count;
    bool visited[100];
    bool directed;
    bool weighted;
public:
    graph(ifstream &fin,bool dir,bool wei){
        directed=dir;
        weighted=wei;
        int a,b;
        fin>>a>>b;
        node_count=a;
        edge_count=b;
        for(int i=0;i<=node_count;i++){
            visited[i]=0;
            for(int j=0;j<=node_count;j++){
                g[i][j]=0;
            }
        }
    }

    void input(ifstream &fin){
        if(directed)
            cout<<"Directed ";
        else
            cout<<"Undirected ";
        if(weighted)
            cout<<"weighted graph\n";
        else
            cout<<"unweighted graph\n";
        int a,b,w;
        w=1;
        for(int i=0;i<edge_count;i++){
            fin>>a>>b;
            a--;
            b--;
            if(weighted)
                fin>>w;
            g[a][b]=w;
            if(!directed)
                g[b][a]=w;
        }
    }
    void show_matrix(int matrix[100][100]){
        for(int i=0;i<node_count;i++){
            for(int j=0;j<node_count;j++)
                cout<<matrix[i][j]<<" ";
            cout<<endl;
        }

    }

    void bfs(int starting_node){
        queue <int> q;
        visited[starting_node]=1;
        q.push(starting_node);
        while (!q.empty()){
            int x=q.front();
            q.pop();
            cout<<x<<" ";
            for(int i=node_count-1;i>=0;i--){
                if(g[x][i]!=0 && !visited[i]){
                    q.push(i);
                    visited[i]=1;
                }
            }
        }
    }
    void dfs_iterativ(int starting_node){
        stack <int> q;
        visited[starting_node]=1;
        q.push(starting_node);
        while (!q.empty()){
            int x=q.top();
            q.pop();
            cout<<x<<" ";
            for(int i=node_count-1;i>=0;i--){
                if(g[x][i]!=0 && !visited[i]){
                    q.push(i);
                    visited[i]=1;
                }
            }
        }
    }
    void dfs_recursiv(int starting_node){
        int x=starting_node;
        cout<<x<<" ";
        visited[x]=1;
        for(int i=0;i<node_count;i++)
            if(g[x][i]!=0 && !visited[i])
                dfs_recursiv(i);
    }
    void floyd_warshall(){
        int d[100][100];
        for(int i=1;i<=node_count;i++){
            for(int j=1;j<=node_count;j++){
                if(g[i][j]==0)
                    d[i][j]=INT_MAX/2;
                else
                    d[i][j]=g[i][j];
                if(i==j)
                    d[i][j]=0;
            }
        }
        for(int k=1;k<=node_count;k++)
            for(int i=1;i<=node_count;i++)
                for(int j=1;j<=node_count;j++)
                    if(d[i][j]>d[i][k]+d[k][j])
                        d[i][j]=d[i][k]+d[k][j];

        for(int i=1;i<=node_count;i++){
            for(int j=1;j<=node_count;j++)
                cout<<d[i][j]<<" ";
            cout<<endl;
        }
    }

    void dijkstra(int starting_node){
        /*vector <int> d;
        vector <int> prev;
        d.resize(node_count+1);
        prev.resize(node_count+1);
        d.assign(node_count,INT_MAX/2);
        priority_queue <ip,vector<ip>,greater<ip> > pq;

        int x=starting_node;
        d[x]=0;
        pq.push({0,x});  ///0=dist from starting node and x is the node
        while(!pq.empty()){
            x=pq.top().second;
            for(int i=0;i<node_count;i++){
                if(g[x][i]!=0 && !visited[i])    ///daca exista muchia si nu a mai fost vizitata
                    if(d[x]+g[x][i]<d[i]){
                        d[i]=d[x]+g[x][i];
                        visited[x]=1;
                        prev[i]=x;
                        //pq.push(i);
                    }
            }

        }*/

        vector <int> d;
        vector <int> prev;
        d.resize(node_count+1);
        prev.resize(node_count+1);
        d.assign(node_count,INT_MAX);
        priority_queue <int,vector<int>,greater<int> > pq;
        int x=starting_node;
        prev[x]=-1;
        d[x]=0;
        pq.push(x);
        while(!pq.empty()){
            x=pq.top();
            pq.pop();
            for(int j=0;j<node_count;j++)
                if(g[x][j]!=0 && !visited[j]){
                    pq.push(j);
                    if(d[x]+g[x][j]<d[j]){
                        d[j]=d[x]+g[x][j];
                        prev[j]=x;
                    }
                visited[x]=1;
                }
        }
        for(int i=0;i<node_count;i++)
            cout<<d[i]<<" ";
        cout<<endl;
        x=2;
        while(x!=-1){
            cout<<x<<" ";
            x=prev[x];
        }

    }

    pair<int,int> find_min_node(vector <int> nodes_to_search){
        int min=INT_MAX;
        pair<int,int> rv;
        int current_node;
        for(int i=0;i<nodes_to_search.size();i++){
            current_node=nodes_to_search[i];  ///selected a node
            for(int j=0;j<node_count;j++){   ///search for the lowest edge connected to the selected node that isn't connected to a visited node
                if(g[current_node][j]!=0 && !visited[j])
                    if(g[current_node][j]<min){
                        min=g[current_node][j];
                        rv.first=current_node;
                        rv.second=j;
                    }
            }
        }
        return rv;
    }

    void prim(int starting_node){
        int new_g[100][100];
        for(int i=0;i<node_count;i++)
            for(int j=0;j<node_count;j++)
                new_g[i][j]=0;
        vector <int> nodes_to_search;
        nodes_to_search.push_back(starting_node);
        visited[starting_node]=1;
        for(int i=0;i<node_count-1;i++){
            pair<int,int> result=find_min_node(nodes_to_search);  ///found a node to connect to
            int a=result.first;
            int b=result.second;
            new_g[a][b]=g[a][b];
            new_g[b][a]=new_g[a][b];
            cout<<a<<" -> "<<b<<"  weight="<<g[a][b]<<endl;
            nodes_to_search.push_back(b);
            visited[b]=1;
        }
        show_matrix(g);
        cout<<endl;
        show_matrix(new_g);
    }

    bool check_if_any_unmarked(vector <bool> arr){
        for(int i=0;i<arr.size();i++)
            if(arr[i]==0)
                return 1;     ///at least one unmarked so true
        return 0;
    }

    void visit(int node,vector <bool> &permanent,vector <bool> &temporary,vector <int> &sorted_nodes){
        if(permanent[node])
            return;
        if(temporary[node]){
            cout<<"Not a DAG";
            exit(1);
        }
        temporary[node]=1;
        for(int i=0;i<node_count;i++)
            if(g[node][i]!=0)
                visit(i,permanent,temporary,sorted_nodes);
        temporary[node]=0;
        permanent[node]=1;
        sorted_nodes.push_back(node+1);

    }
    void topSort(ofstream &fout){
        int sum=0;
        int x=-1;
        show_matrix(g);
        for(int i=0;i<node_count;i++){
            for(int j=0;j<node_count;j++)
                sum+=g[j][i];
            if(sum==0){
                x=i;
                break;
            }
            sum=0;
        }
        vector <int> sorted_nodes;
        vector <bool> permanent;
        vector <bool> temporary;
        permanent.assign(node_count,0);
        temporary.assign(node_count,0);
        int i;
        while(check_if_any_unmarked(permanent)){
            for(i=0;i<node_count;i++)
                if(!permanent[i]){
                    break;
                }
            visit(i,permanent,temporary,sorted_nodes);
            for(int j=0;j<sorted_nodes.size();j++)
                fout<<sorted_nodes[j]<<" ";
        }


    }

};

int main()
{
    ifstream fin("sortare.in");
    ofstream fout("sortare.out");

    graph test(fin,1,0);
    test.input(fin);
    //test.dfs_iterativ(0);
    //test.floyd_warshall();
    //test.prim(0);
    test.topSort(fout);
    return 0;
}