#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define inf 1061109567
#define nmax 50005

using namespace std;

int n, m;

vector< pair<int, int> > a[nmax];
int dist[nmax];

void citire()
{
    freopen("dijkstra.in", "r", stdin);
    scanf("%d%d", &n, &m);
    int x, y, cost;
    for (int i=0; i<m; ++i)
    {
        scanf("%d%d%d", &x, &y, &cost);
        a[x].push_back(make_pair(y, cost));
    }
}

void dijkstra()
{
    bool use[nmax];
    queue<int> q;

    memset(dist, inf, sizeof(dist));
    memset(use, false, sizeof(use));

    dist[1]=0; q.push(1); use[1]=true;

    while (!q.empty())
    {
        int nod=q.front();
        q.pop();
        use[nod]=false;

        for(vector< pair<int, int> >::iterator it=a[nod].begin(); it!=a[nod].end(); ++it)
            if (dist[nod] + it->second < dist[it->first])
            {
                dist[it->first] = dist[nod] + it->second;
                if (!use[it->first]) {
                    q.push(it->first);
                    use[it->first] = true;
                }
            }
    }
}

void afisare()
{
    freopen("dijkstra.out", "w", stdout);

    for(int i=2; i<=n; ++i)
    printf("%d ", (dist[i]<inf?dist[i]:0));

}

int main()
{
    citire();
    dijkstra();
    afisare();
}