#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int main()
{
    int n,m;
    in>>n>>m;
    int inf=20001;
    vector<vector<pair<int,int>>> Graf(n+1);
    queue<int> q;
    vector <int> dist(n+1,inf);
    dist[1]=0;
    vector<int >viz(n+1,0);
    viz[1]=0;
    int vizitate=1;


    for(int i=0;i<m;i++)
    {
        int a,b,c;
        in>>a>>b>>c;
        Graf[a].push_back({b,c});
    }
    int nod_curent=1;
    while(vizitate!=n)
    {
        for(auto i:Graf[nod_curent])
            if(dist[nod_curent]+i.second<dist[i.first])
            {
                dist[i.first]=dist[nod_curent]+i.second;
            }
        int minim=1000;
        int ind_min=-1;
        for(int i=1;i<=n;i++)
        {
            if(dist[i]<minim && viz[i]==0)
            {
                ind_min=i;
                minim=dist[i];
            }
        }
        nod_curent=ind_min;
        viz[nod_curent]=1;
        vizitate++;

    }
    for(int i=2;i<=n;i++)
        out<<dist[i]<<" ";


}