import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static class Route{
		public int targetCity;
		public int value;
		public int getTargetCity() {
			return targetCity;
		}
		public void setTargetCity(int targetCity) {
			this.targetCity = targetCity;
		}
		public int getValue() {
			return value;
		}
		public void setValue(int value) {
			this.value = value;
		}
		
	}
	
	static class City{
		public List<Route> routes;

		public List<Route> getRoutes() {
			return routes;
		}

		public void setRoutes(List<Route> routes) {
			this.routes = routes;
		}
		
	}
	
	static class TradeServiceImpl {

		private final static int N_MAX = 50010;
		private Queue<Integer> queue = new LinkedList<Integer>();
		private boolean[] contains = new boolean[N_MAX];
		private int[] distance = new int[N_MAX];
		private boolean cicle = false;
		private int[] count = new int[N_MAX];
		{
			Arrays.fill(distance, Integer.MAX_VALUE);
		}

		public int[] analyzeRoutes(City[] cities) {
			queue.add(0);
			contains[0] = true;
			distance[0] = 0;
			int size = cities.length;

			while (!queue.isEmpty() && !cicle) {
				int index = queue.poll();
				City city = cities[index];
				contains[index] = false;
				if (distance[index] == Integer.MAX_VALUE) {
					continue;
				}
				for (Route route : city.getRoutes()) {
					if (distance[route.getTargetCity()] > distance[index] + route.getValue()) {
						distance[route.getTargetCity()] = distance[index] + route.getValue();
						if (contains[route.getTargetCity()]) {
							continue;
						}
						if (count[route.getTargetCity()] > size) {
							return new int[]{-1};
						}
						queue.add(route.getTargetCity());
						contains[route.getTargetCity()] = true;
						count[route.getTargetCity()]++;
					}
				}
			}
			return Arrays.copyOfRange(distance, 1, size);
		}
	}
	
  private static City[] cities;

  public static void main(String[] args) throws FileNotFoundException {
//    generate();
    readInput();
    TradeServiceImpl tradeService = new TradeServiceImpl();
    int output[] = tradeService.analyzeRoutes(cities);
    writeOutput(output);
  }


  private static void writeOutput(int[] output) {
    try (PrintWriter writer = new PrintWriter("bellmanford.out");) {
    	if(output.length ==1 && output[0]==-1){
    		writer.print("Ciclu negativ!");
    	}else{
    		for(int i=0;i<output.length;i++){
    			writer.printf("%d ", output[i]);
    		}
    	}
    } catch (IOException e) {
      e.printStackTrace();
    }
  }



  private static void readInput() throws FileNotFoundException {
    try (Scanner scanner = new Scanner(new FileInputStream("bellmanford.in"));) {
      int numberOfCities = scanner.nextInt();
      int numberOfRoutes = scanner.nextInt();
      cities = new City[numberOfCities];
      for (int i = 0; i < numberOfCities; ++i) {
        cities[i] = new City();
        cities[i].setRoutes(new ArrayList<Route>());
      }
      for (int i = 0; i < numberOfRoutes; ++i) {
        int source = scanner.nextInt() - 1;
        int target = scanner.nextInt() - 1;
        int value = scanner.nextInt();
        Route route = new Route();
        route.setTargetCity(target);
        route.setValue(value);
        cities[source].getRoutes().add(route);
      }
    }
  }
}