#include <fstream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int INF = 1 << 30;
const int MAX = 50000;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct Vertex
{
    int nod;
    int weight;
    Vertex *next;
};

Vertex *G[MAX + 1];

bool visited[MAX + 1];
int dist[MAX + 1];
int m, n;

void addVertex(int a, int b, int w)
{
    Vertex *p = new Vertex;
    p -> nod = b;
    p -> weight = w;
    p -> next = G[a];
    G[a] = p;
}

void readGraph()
{
    in >> n >> m;

    int a, b, w;
    for (int i = 1; i <= m; i++)
    {
        in >> a >> b >> w;
        addVertex(a, b, w);
    }
}

void Dijkstra(int source)
{
    for (int i = 1; i <= n; i++)
      dist[i] = INF;

    dist[source] = 0;

    priority_queue<int, vector<int>, greater<int> > Coada;
    for (int i = 1; i <= n; i++)
            Coada.push(i);

    while (!Coada.empty())
    {
        int current = Coada.top();
        Coada.pop();
        visited[current] = true;
        for (Vertex *p = G[current]; p != NULL; p = p -> next)
        {
            if (dist[p -> nod] > dist[current] + (p -> weight) )
            {
                dist[p -> nod] = dist[current] + (p -> weight);
            }
        }
    }
}

void printDist(int source)
{
    for (int i = 1; i <= n; i++)
    {
        if (i != source)
        {
            out << dist[i] << " ";
        }
    }
}

int main()
{
    readGraph();
    Dijkstra(1);
    printDist(1);

    return 0;
}