#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
int x, y, cost, nod, i, n, m, val, dist[1005];
vector <pair <int, int> > g[1005];
pair <int, int> vic;

queue <int> q;
int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin>>n>>m;
    //g.resize(n+1);
    //d.resize(n+1);
    for (i=1; i<=m; ++i)
    {
        cin>>x>>y>>cost;
        vic=make_pair(y,cost);
        g[x].push_back(vic);
    }

    for (i=1; i<=n; ++i)
        dist[i]=INF;
    q.push(1);
    dist[1]=0;
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        // for ( val=1;val<=G[x].size();val++ )
        //for (const auto i:g[x])
            //for(pair<int,int>::iterator val=G[x].begin();val!=G[x].end();val++)
            for(val=0;val<g[x].size();val++)

        {
            nod=g[x][val].first;
            cost=g[x][val].second;
            if (dist[nod]>dist[x]+cost )
            {
                dist[nod]=dist[x]+cost;
                q.push(nod);
            }
        }
    }

    for (i=2; i<=n; ++i)
        if (dist[i]==INF)
            cout<<0<<' ';
        else
            cout<<dist[i]<<' ';
    return 0;
}