#include <fstream>

using namespace std;

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

const int MAX_N = 50000;
const long long INF = 1000000000000;

template<typename T>
struct List
{
    struct Node
    {
        T val;
        Node* next;
    };
    Node* head;
    Node* tail;

    List(): head(NULL), tail(NULL) {}

    void PushBack(T val)
    {
        Node* curr = new Node{ val, NULL };
        if(head == NULL && tail == NULL)
        {
            head = tail = curr;
            return;
        }
        tail->next = curr;
        tail = curr;
    }
};

struct Item
{
    int node;
    long long cost;

    bool operator<(const Item& obj) const
    {
        return cost < obj.cost;
    }
};

struct MinHeap
{
    Item heap[MAX_N + 1];
    int n;

    inline bool Empty() const
    {
        return n == 0;
    }

    inline Item Min() const
    {
        return heap[1];
    }

    void PushDown(int node)
    {
        int son;
        while((son = node << 1) <= n)
        {
            if(son < n && heap[son + 1] < heap[son])
                son++;
            if(heap[node] < heap[son])
                break;
            swap(heap[node], heap[son]);
            node = son;
        }
    }

    void PushUp(int node)
    {
        int father;
        while((father = node >> 1) > 0 && heap[node] < heap[father])
        {
            swap(heap[node], heap[father]);
            node = father;
        }
    }

    void Erase()
    {
        heap[1] = heap[n];
        n--;
        PushDown(1);
    }

    void Insert(Item item)
    {
        n++;
        heap[n] = item;
        PushUp(n);
    }
};

List<Item> adj[MAX_N + 1];
long long dist[MAX_N + 1];
MinHeap minHeap;
int n, m;

void ReadGraph()
{
    fin >> n >> m;
    while(m--)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        adj[x].PushBack({ y, cost });
    }
}

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

void Dijkstra(int source)
{
    dist[source] = 0;
    minHeap.Insert({ source, dist[source] });

    while(!minHeap.Empty())
    {
        Item item = minHeap.Min();
        minHeap.Erase();

        for(List<Item>::Node* it = adj[item.node].head; it; it = it->next)
            if(item.cost + it->val.cost < dist[it->val.node])
            {
                dist[it->val.node] = item.cost + it->val.cost;
                minHeap.Insert({ it->val.node, dist[it->val.node] });
            }
    }
}

void WriteDist(int source)
{
    for(int i = 1; i <= n; i++)
        if(i != source)
            fout << ((dist[i] == INF) ? 0 : dist[i]) << ' ';
    fout << '\n';
}

int main()
{
    ReadGraph();
    Init();
    Dijkstra(1);
    WriteDist(1);

    fin.close();
    fout.close();

    return 0;
}