Graphs

// //dfs code for cycle detection
// Vi vis(N);
// vector<int> vis(MX);
// vector<int> adj[MX]
// Void dfs(int node, int root)
// {
// 	vis[node] = 1;
// 	for (int i = 0; i < adj[node].size(); i++)
// 	{
// 		if (vis[adj[node][i]] == 0)
// 		{
// 			cout << adj[node][i] << endl;
// 			dfs(adj[node][i], node);

// 		}
// 		else if (vis[adj[node][i]] == 1 && adj[node][i] != root)
// 		{
// 			cout << ”Cycle detected” << endl;
// 			exit(0);
// 		}

// 	}
// }
// int main()
// {
// 	int nodes, edges;
// 	cin >> nodes >> edges;
// 	for (int i = 0; i < edges; i++)
// 	{
// 		int u, v;
// 		cin >> u >> v;
// 		adj[u].push_back(v);
// 		adj[v].push_back(u);
// 	}
// 	dfs(1, 1);
// }
///dfs code
/*HAR HAR MAHADEV
ヽ｀、ヽ｀｀、ヽ｀ヽ｀、、ヽ ｀ヽ 、ヽ｀🌙｀ヽヽ｀ヽ、ヽ｀
ヽ｀、ヽ｀｀、ヽ 、｀｀、 ｀、ヽ｀ 、｀ ヽ｀ヽ、ヽ ｀、ヽ｀｀、
ヽ、｀｀、｀、ヽ｀｀、 、ヽヽ｀、｀、、ヽヽ、｀｀、 、 ヽ｀、
ヽ｀｀、 ヽ｀ヽ｀、、ヽ ｀ヽ 、 🚶ヽ｀｀｀｀ヽヽヽ｀、、ヽ｀、、ヽ*/
# include   <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;//typedef for datatype and #define for macro

# define    fast                ios_base::sync_with_stdio(false);cin.tie(NULL);
# define    MOD                 1000000007
# define    endl                '\n'
# define    FOR(i, a, b)        for (int i=a; i<(b); i++)
# define    F0R(i, a)           for (int i=0; i<(a); i++)
# define    FORd(i,a,b)         for (int i = (b)-1; i >= a; i--)
# define    F0Rd(i,a)           for (int i = (a)-1; i >= 0; i--)
# define    INF                 9e18
# define    PI                  3.14159265358979323846
# define    lb                  lower_bound
# define    ub                  upper_bound
# define    mp                  make_pair
# define    pb                  push_back
# define    fi                  first
# define    se                  second
# define    all(a)              a.begin(), a.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const       int                 MX = 100001;
// vector<int> vis(MX);
// vector<int> adj[MX]
// Void dfs(int node)
// {
// 	vis[node] = 1;
// 	for (int i = 0; i < adj[node].size(); i++) /// for(auto &i : adj[node])
// 	{
// 		if (vis[adj[node][i]] == 0)		// vis[i]=0
// 		{
// 			cout << adj[node][i] << endl;	//
// 			dfs(adj[node][i]);
// 		}
// 	}
// }
// int main()
// {
// 	int nodes, edges;
// 	cin >> nodes >> edges;
// 	for (int i = 1; i <= edges; i++) //dfs of graph(unidirectional)
// 	{
// 		int u, v;
// 		cin >> u >> v;
// 		adj[u].push_back(v);
// 		adj[v].push_back(u);
// 	}
// 	// if 1 is root node
// 	dfs(1);
// }
vector<int> vis(MX);
vector<pair<int, int>> v[MX];
// void dfs(int node)
// {
// 	vis[node] = 1;
// 	int i;
// 	for (i = 0; i < v[node].size(); i++)
// 	{
// 		if (vis[v[node][i]] == 0)//not visited
// 		{
// 			cout << v[node][i] << " " << endl;
// 			dfs(v[node][i]);
// 		}
// 	}
// }
void dfs(int node, int root)
{
	vis[node] = 1;
	int i;
	for (i = 0; i < v[node].size(); i++)
	{
		if (root == v[node][i])
		{
			continue;
		}
		if (vis[v[node][i]] == 0)//not visited
		{
			cout << v[node][i] << " " << endl;
			dfs(v[node][i], node);
		}
		else if (vis[v[node][i]] == 1)
		{
			cout << "cycle found" << endl;
		}
	}
}
int main()
{
	cout << "enter the number of node: " << endl;
	int nodes, edges, i;
	cin >> nodes;
	cout << "enter the number of edges: " << endl;
	cin >> edges;
	cout << "enter the edges: " << endl;
	for (i = 0; i < edges; i++)
	{
		int a, b, w;
		cin >> a >> b >> w;
		v[a].emplace_back(b, w);
		v[b].push_back(make_pair(a, w));
	}
	//calling dfs function;
	cout << 1 << endl;
	dfs(1, 1);
	/// if 1 is a root node;\
	// queue<int> q;
	// q.push(1);
	// vis[1] = 1;
	// while (q.size() != 0)
	// {
	// 	int k = q.front();
	// 	q.pop();
	// 	for (int i = 0; i < v[k].size(); i++)
	// 	{
	// 		if (!vis[v[k][i]])
	// 		{
	// 			vis[v[k][i]] = 1;
	// 			q.push(v[k][i]);
	// 		}
	// 	}
	// }
	return 0;
}

/////////////////////////bfs///////////////////////////////////
// queue<int> q;
// q.push(si);
// vis[si]=1;
// while(!q.empty())
// {
// 	int S=q.front();
// 	q.pop();
// 	for(auto& i:S)
// 	{
// 		if(!vis[i])
// 		{
// 			vis[i]=1;
// 			q.push(i);
// 		}
// 	}
// }

////////////////////////all paths from src to target
// vector<int> stk;
// vector<vector<int>> ans;
// class Solution
// {
// public:
// void dfs(int src, int target, vector<vector<int>>& adj)
// {
//     // vis[src] = 1;
//     for (auto i : adj[src])
//     {
//         if (i == target)
//         {
//             stk.push_back(i); ans.push_back(stk); stk.pop_back();
//             continue;
//         }
//         else
//         {
//             stk.push_back(i);
//             dfs(i, target, adj);
//             // vis[i]=0;
//         }
//         stk.pop_back();
//     }
// }
//     vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& adj)
//     {
//         stk.clear(); ans.clear();
//         // vector<int> vis(adj.size(), 0);
//         stk.push_back(0);
//         dfs(0, adj.size()-1, adj);
//         return ans;
//     }
// };