#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct heapnode
{
    int nod;
    long long dist_total;
    bool operator <(const heapnode &other) const
    {
        return dist_total>other.dist_total;
    }
};
priority_queue <heapnode> q;
struct path
{
    int cost, nod;
};

vector <path> ma[50005];
long long dist[50005];

void dijkstra (int n)
{
    heapnode prim;
    prim.nod=1;
    prim.dist_total=0;
    q.push(prim);
    while(!q.empty()) //nu e gol
    {
        heapnode top = q.top();
        q.pop();
        if( dist[top.nod] < top.dist_total)
            continue;
        int p=ma[top.nod].size();
        for(int i=0; i<p; ++i)
        {
            int destinatie = ma[top.nod][i].nod;
            int cost = ma[top.nod][i].cost;
            if(top.dist_total+cost < dist[destinatie])
            {
                dist[destinatie] = top.dist_total+cost;
                heapnode vecin;
                vecin.nod=destinatie;
                vecin.dist_total=dist[destinatie];
                q.push(vecin);
            }
        }
    }

}

const int MAX = 1000000000;
int main()
{
    int n,m;
    in>>n>>m;
    for(int i=1; i<=n; ++i)
        dist[i]=MAX;
    for(int i=1; i<=m; ++i)
    {
        int a,b,c;
        //c este cost
        in>>a>>b>>c;
        path x;
        x.nod=b;
        x.cost=c;
        ma[a].push_back(x);
    }
    dijkstra(n);
    for(int i=2; i<=n; ++i)
    {
        if(dist[i]==MAX)
            dist[i]=0;
        out<<dist[i]<<" ";
    }
    return 0;
}