#include <fstream>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

const int MAXN=5004;
const int INF=0x3f3f3f3f;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct vecin{
    int y,cost;
    bool operator <(const vecin& other) const
    {   if(cost != other.cost)
            return cost<other.cost;
        return y<other.y;
    }
};

int n,m,dmin[MAXN];

vector<vecin>graf[MAXN];
set<vecin>q;

void solve()
{
    for(int i=2;i<=n;i++)
    {
        dmin[i]=INF;
    }
    q.insert({1,0});
    while (!q.empty())
    {
        int top=q.begin()->y;
        q.erase(q.begin());
        
         for(const vecin& v:graf[top])
         {
             int nc=dmin[top]+v.cost;
             if(dmin[v.y]>nc)
             {
                 if(dmin[v.y]!=INF)
                     q.erase({v.y,dmin[v.y]});
                 dmin[v.y]=nc;
                 q.insert({v.y,dmin[v.y]});
             }
         }
    }
}

int main( ) {
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        graf[x].push_back({y,c});
    }
    solve();
    for(int i=2;i<=n;i++)
        if(dmin[i]==INF)
            fout<<"0"<<" ";
    else
        fout<<dmin[i]<<" ";
    return 0;
}