#include <fstream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;

const int MAX = 50005;
const int INF = 0x3f3f3f3f;
int dMin[MAX], n, m;
bool inQueue[MAX];
vector< pair <int , int> > G[MAX];


void citire()
{
    ifstream in("dijkstra.in");
    in>>n>>m;
    int a, b, x;
    for(int i = 1; i <= m; i++)
    {
        in>>a>>b>>x;
        G[a].push_back(make_pair(b, x));
    }
    in.close();
}

void solve()
{
    bool inQueue[MAX]; int nod;
    queue<int> Q;
    memset(inQueue, false, sizeof(inQueue));
    memset(dMin, INF, sizeof(dMin));
    Q.push(1); inQueue[1] = true; dMin[1] = 0;
    while(!Q.empty())
    {
        nod = Q.front(); Q.pop(); inQueue[nod] = false;
        for(vector< pair< int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); it++)
        {
            if(dMin[nod] + (*it).second < dMin[(*it).first])
            {
                dMin[(*it).first] = dMin[nod] + (*it).second;
                if(!inQueue[(*it).first])
                {
                    Q.push((*it).first);
                    inQueue[(*it).first] = true;
                }
            }
        }
    }
}

void afisare()
{
    ofstream out("dijkstra.out");
    for(int i = 2; i <= n; i++)
        out<< (dMin[i] < INF ? dMin[i] : 0)<<" ";
    out.close();
}


int main()
{
    citire();
    solve();
    afisare();
    return 0;
}