#include <iostream>
#include <queue>
#include <fstream>

#define INF 2000000000
using namespace std;

int n,m;

queue <int> c;
ifstream be("dijkstra.in");
ofstream ki("dijkstra.out");

class ut
{
public:
    int to;
    short x;
};

class pont
{
public:
    vector <ut> utak;
    int best = INF;
}t[50001];

void beolvas()
{
    int x;
    ut y;
    be>>n>>m;
    for(int i = 0; i < m;i++)
    {
        be>>x>>y.to>>y.x;
        t[x].utak.push_back(y);
    }
}

void dijkstra()
{
    c.push(1);
    t[1].best = 0;
    while(!c.empty())
    {
        int now = c.front();
        c.pop();
        int meret = t[now].utak.size();
        for(int i = 0; i < meret;i++)
        {
            if( t[now].best + t[now].utak[i].x < t[t[now].utak[i].to].best)
            {
                t[t[now].utak[i].to].best = t[now].best + t[now].utak[i].x;
                c.push(t[now].utak[i].to);
            }
        }
    }
}

void kiiras()
{
    for(int i = 2; i < n +1 ;i++)
        ki << t[i].best<<" ";
}

int main()
{
    beolvas();
    dijkstra();
    kiiras();

    return 0;
}