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

using namespace std;

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

struct HeapNode
{
    int nod, dist_tot;
    bool operator <(const HeapNode &other) const
    {
        return dist_tot>other.dist_tot;
    }
};

priority_queue <HeapNode> pq;

struct drum
{
    int cost, nod;
};

vector <drum> matad[50005];
long long dist[50005];

void dijkstra(int n)
{
    HeapNode prim;
    prim.nod=1;
    prim.dist_tot=0;
    pq.push(prim);
    while(!pq.empty())
    {
        HeapNode top=pq.top();
        //if()
        pq.pop();
        for(int i=0; i<matad[top.nod].size(); i++)
        {
            int destinatie=matad[top.nod][i].nod;
            int costdestinatie=matad[top.nod][i].cost;

            if(top.dist_tot+costdestinatie<dist[destinatie])
            {
                dist[destinatie]=top.dist_tot+costdestinatie;
            }

            HeapNode vecin;
            vecin.nod=destinatie;
            vecin.dist_tot=dist[destinatie];
            pq.push(vecin);//adaug urmatoarea chestie in pq
        }
    }
}

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=1; i<=n; i++)
        dist[i]=0x3f3f3f3f;

    for(int i=1; i<=m; i++)
    {
        int a,b,cost;
        cin>>a>>b>>cost;
        drum x;
        x.nod=b;
        x.cost=cost;
        matad[a].push_back(x);
    }
    dijkstra(n);
    for(int i=2; i<=n; i++)
    {
        cout<<dist[i]<<" ";
    }
    return 0;
}