#include <fstream>
#include <vector>

using namespace std;

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

const int MAX_N = 50000;
const int INF = 1000000000;

struct Item
{
    int cost, node;

    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);
    }
};

vector<Item> adj[MAX_N + 1];
int 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].push_back({ cost, y });
    }
}

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

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

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

        for(Item it : adj[item.node])
            if(item.cost + it.cost < dist[it.node])
            {
                dist[it.node] = item.cost + it.cost;
                minHeap.Insert({ dist[it.node], it.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;
}