import java.io.*;
import java.util.Date;
import java.util.Random;

class Int
{
  int i;
  
  Int(int i)
  {
    this.i = i;
  }
}

class IO
{

  public static int readInt() 
  // Reads an int from standard input.
  {
    String input = "";
    try 
    {
      BufferedReader bufRead = new BufferedReader
        (new InputStreamReader (System.in));
      input = bufRead.readLine();
    } 
    catch (java.io.IOException e) 
    {
      System.out.print("Error while reading input line!\n");
    }
    return Integer.valueOf(input).intValue();
  }
} 

class Clock 
{
  static long now()
  // returns the current time in miliseconds
  {
    return (new Date()).getTime();
  }
}

class QuickSort
{
  static private void sort(int[] a, int l, int h, Random random)
  // Sort h - l + 1 elements of a[] running from l to h
  {
    if (h > l) // At least two elements
      if (h == l + 1) // Exactly two elements
      {
        if (a[l] > a[h])
        {
          int x = a[l]; a[l] = a[h]; a[h] = x; 
        }
      }
      else            // More than two elements
      {
        int s = a[l + random.nextInt(h - l + 1)];
        int low = l; 
        int hgh = h;

        // Splitting
        while (low < hgh) 
        {
          while (low <= h && a[low] < s)
            low++;
          while (hgh >= l && a[hgh] > s)
            hgh--;
          if (low <= hgh) // swap a[low] and a[hgh]
          {
            int x = a[low]; a[low] = a[hgh]; a[hgh] = x; 
            low++;
            hgh--;
          } 
        }

        // Recursion
        sort(a, l, hgh, random);
        sort(a, low, h, random);
      }
  }

  static void sort(int[] a, int n)
  {
    Random random = new Random(Clock.now());
    sort(a, 0, n - 1, random);
  }
}

class Queue
{
  private int       h;
  private int       t;
  private int       n;
  private int[]     a;
  private boolean[] b; // indicating whether element is in queue
  private int       c; // number of elements in queue

  Queue(int n)
  {
    this.n = n;
    h      = 0;
    t      = 0;
    a      = new int[n];
    b      = new boolean[n];
    c      = 0;
    for (int i = 0; i < n; i++)
      b[i] = false;
  }

  void enqueue(int x)
  {
    a[h] = x;
    h++;
    if (h == n)
      h = 0;
    b[x] = true;
    c++;
  }
  
  int dequeue()
  {
    int x = a[t];
    t++;
    if (t == n)
      t = 0;
    b[x] = false;
    c--;
    return x;
  }

  boolean isInQueue(int i)
  {
    return b[i];
  }

  boolean notEmpty()
  {
    return c > 0;
  }
}

class WeightedGraph
{
  private int   n;
  private int   m;
  private int[] f;      // Starting indices
  private int[] a;      // Neighbors
  private int[] weight; // Weights

  WeightedGraph(int n, int m)
  {
    this.n = n;
    this.m = m;
    f      = new int[n + 1];
    a      = new int[m];
    weight = new int[m];

    Random random = new Random(Clock.now());
    f[0] = 0;
    for (int i = 1; i <  n; i++)
      f[i] = random.nextInt(m);
    f[n] = m;
    QuickSort.sort(f, n + 1);
    for (int j = 0; j < m; j++)
    {
      a[j]      = random.nextInt(n);
      weight[j] = random.nextInt(100) - 10;
    }
  }

  void print()
  {
    System.out.println();
    for (int i = 0; i < n; i++)
    {
      System.out.print("node " + i + " -> ");
      for (int j = f[i]; j < f[i + 1]; j++)
        System.out.print(" (" + a[j] + ", " + weight[j] + ")");
      System.out.println();
    }
   
  }

  void negativelyWeightedSSSP(int s, int[] dist) 
  {
    final int INFINITY = 9999;
    for (int v = 0; v < n; v++)
      dist[v] = INFINITY; 
    Queue q = new Queue(n);
    dist[s] = 0;
    q.enqueue(s);
    while (q.notEmpty()) 
    {
      int v = q.dequeue();
      for (int j = f[v]; j < f[v + 1]; j++)
      {
        int w = a[j];
        if (dist[w] > dist[v] + weight[j]) // shorter path
        {
          dist[w] = dist[v] + weight[j];
          if (! q.isInQueue(w))
            q.enqueue(w);
        }
      }
    } 
  } 
}

class BellmanTest
{
  static void print(long t, int n, int[] number)
  {
    if (n < 100)
    {
      System.out.println("Computing numbers took " + t 
        + " milliseconds:");
      for (int i = 0; i < n; i++)
        System.out.println("number[" + i + "] = " + number[i]);
    }
    else
      System.out.println("Computing numbers took " + t 
        + " milliseconds");
  }

  public static void main(String[] args)
  {
    Random random = new Random(Clock.now());
    System.out.print("\nGive n       >>>   ");
    int n = IO.readInt();
    System.out.print("Give m       >>>   ");
    int m = IO.readInt();
    WeightedGraph graph = new WeightedGraph(n, m);
    if (n < 100)
      graph.print();
    int [] dist = new int[n];

    System.out.println();
    long t = - Clock.now();
    graph.negativelyWeightedSSSP(0, dist);
    t += Clock.now();
    print(t, n, dist);

    System.out.println();
  }
}