{"id":"9b9338cc-0894-4d46-9a28-adfdaf9627f5","name":"Bellman Ford","description":"You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge.\r\nYour task is to find the shortest path from source vertex (vertex number 1) to all other vertices.\r\n\r\nNote : use bellman ford algo.","inputFormat":"First line contains two space separated integers,N and M. Then M lines follow, each line has 3 space separated integers ai, bi and wi.","outputFormat":"Print the shortest distances from the source vertex (vertex number 1) to all other vertices in a line. Print 10^9 in case the vertex can't be reached form the source vertex.","constraints":"1&lt;= N &lt;= 10^4\r\n1&lt;= M &lt;= 10^6\r\n1&lt;= ai, bi &lt;= N\r\n-1000 &lt;= wi &lt;= 1000","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nint main(){\n \n int n,m;\n cin>>n>>m;\n\n vector<vector<int>> edges(m,vector<int>(3));\n \n for(int i=0;i<m;i++){\n int x,y,z;\n cin>>x>>y>>z;\n \n edges[i][0]=x-1;\n edges[i][1]=y-1;\n edges[i][2]=z;\n \n }\n \n} \n "},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.Arrays;\nimport java.util.LinkedList;\n\npublic class Main {\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br=new BufferedReader(new InputStreamReader(System.in));\n String[] st=br.readLine().split(\" \");\n \n int n=Integer.parseInt(st[0]);\n int m=Integer.parseInt(st[1]);\n \n int[][] arr=new int[m][3];\n \n for(int i=0;i<m;i++)\n {\n st=br.readLine().split(\" \");\n arr[i][0]=Integer.parseInt(st[0])-1;\n arr[i][1]=Integer.parseInt(st[1])-1;\n arr[i][2]=Integer.parseInt(st[2]);\n }\n \n \n\t}\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"5 5\r\n1 2 5\r\n1 3 2\r\n3 4 1\r\n1 4 6\r\n3 5 5","sampleOutput":"5 2 3 7 \r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"3ea2fe6b-8196-40cf-b4e4-c059bf2012fd","name":"Bellman Ford","slug":"bellman-ford","type":1}],"next":{"id":"63c2aaec-322d-4597-81ad-02dc1b066659","name":"Bellman Ford 2 MCQ","type":0,"slug":"bellman-ford-2-mcq"},"prev":{"id":"089579c7-8969-471d-8dea-7c8e33ff88b6","name":"Swim in Rising Water","type":3,"slug":"swim-in-rising-water"}}}

Bellman Ford

You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge. Your task is to find the shortest path from source vertex (vertex number 1) to all other vertices. Note : use bellman ford algo.

{"id":"9b9338cc-0894-4d46-9a28-adfdaf9627f5","name":"Bellman Ford","description":"You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge.\r\nYour task is to find the shortest path from source vertex (vertex number 1) to all other vertices.\r\n\r\nNote : use bellman ford algo.","inputFormat":"First line contains two space separated integers,N and M. Then M lines follow, each line has 3 space separated integers ai, bi and wi.","outputFormat":"Print the shortest distances from the source vertex (vertex number 1) to all other vertices in a line. Print 10^9 in case the vertex can't be reached form the source vertex.","constraints":"1&lt;= N &lt;= 10^4\r\n1&lt;= M &lt;= 10^6\r\n1&lt;= ai, bi &lt;= N\r\n-1000 &lt;= wi &lt;= 1000","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nint main(){\n \n int n,m;\n cin>>n>>m;\n\n vector<vector<int>> edges(m,vector<int>(3));\n \n for(int i=0;i<m;i++){\n int x,y,z;\n cin>>x>>y>>z;\n \n edges[i][0]=x-1;\n edges[i][1]=y-1;\n edges[i][2]=z;\n \n }\n \n} \n "},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.Arrays;\nimport java.util.LinkedList;\n\npublic class Main {\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br=new BufferedReader(new InputStreamReader(System.in));\n String[] st=br.readLine().split(\" \");\n \n int n=Integer.parseInt(st[0]);\n int m=Integer.parseInt(st[1]);\n \n int[][] arr=new int[m][3];\n \n for(int i=0;i<m;i++)\n {\n st=br.readLine().split(\" \");\n arr[i][0]=Integer.parseInt(st[0])-1;\n arr[i][1]=Integer.parseInt(st[1])-1;\n arr[i][2]=Integer.parseInt(st[2]);\n }\n \n \n\t}\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"5 5\r\n1 2 5\r\n1 3 2\r\n3 4 1\r\n1 4 6\r\n3 5 5","sampleOutput":"5 2 3 7 \r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"3ea2fe6b-8196-40cf-b4e4-c059bf2012fd","name":"Bellman Ford","slug":"bellman-ford","type":1}],"next":{"id":"63c2aaec-322d-4597-81ad-02dc1b066659","name":"Bellman Ford 2 MCQ","type":0,"slug":"bellman-ford-2-mcq"},"prev":{"id":"089579c7-8969-471d-8dea-7c8e33ff88b6","name":"Swim in Rising Water","type":3,"slug":"swim-in-rising-water"}}}
plane

Editor


Loading...

Bellman Ford

easy

You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge. Your task is to find the shortest path from source vertex (vertex number 1) to all other vertices. Note : use bellman ford algo.

Constraints

1<= N <= 10^4 1<= M <= 10^6 1<= ai, bi <= N -1000 <= wi <= 1000

Format

Input

First line contains two space separated integers,N and M. Then M lines follow, each line has 3 space separated integers ai, bi and wi.

Output

Print the shortest distances from the source vertex (vertex number 1) to all other vertices in a line. Print 10^9 in case the vertex can't be reached form the source vertex.

Example

Sample Input

5 5 1 2 5 1 3 2 3 4 1 1 4 6 3 5 5

Sample Output

5 2 3 7

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode